Code & Fun

第71天。

今天的题目是Find Bottom Left Tree Value:

Given a binary tree, find the leftmost value in the last row of the tree.

Example 1:
Input:

2

/
1 3

Output:
1
Example 2:
Input:

    1
   / \
  2   3
 /   / \
4   5   6
   /
  7

Output:
7
Note: You may assume the tree (i.e., the given root node) is not NULL.

显然这可以用带高度的深度优先去做:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int findBottomLeftValue(TreeNode *root,int &height) {
if (root == nullptr) {
height = -1;
return -1;
}
if (root->left == nullptr && root->right == nullptr)
return root->val;
int lefth,righth;
lefth = righth = height + 1;
int left = findBottomLeftValue(root->left,lefth);
int right = findBottomLeftValue(root->right,righth);
if (lefth >= righth) {
height = lefth;
return left;
} else{
height = righth;
return right;
}
}
int findBottomLeftValue(TreeNode* root) {
int h = 0;
return findBottomLeftValue(root,h);
}

看起来就不优雅,而且很繁琐的样子,下面是dicuss中用广度优先去做的:

1
2
3
4
5
6
7
8
9
10
11
12
public int findLeftMostNode(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
root = queue.poll();
if (root.right != null)
queue.add(root.right);
if (root.left != null)
queue.add(root.left);
}
return root.val;
}

以及python版本:

1
2
3
4
5
def findLeftMostNode(self, root):
queue = [root]
for node in queue:
queue += filter(None, (node.right, node.left))
return node.val

本文首发于Code & Fun