第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
|