1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
private int deepest;
private int ans;
public int findBottomLeftValue(TreeNode root) {
deepest = -1;
dfs(root, 0);
return ans;
}
private void dfs(TreeNode node, int depth) {
if (node == null) {
return;
}
dfs(node.left, depth + 1);
dfs(node.right, depth + 1);
if (node.left == null && node.right == null && depth > deepest) {
ans = node.val;
deepest = depth;
}
}
}
|
答案肯定是leaf node. 于是我们先走左边, 再走右边. 然后最后看自己是不是leaf node, 如果是并且depth比当前遇到的最深的还要深, 那么更新ans和deepest. 需要注意的是等于deepest的时候不能更新ans, 因为我们求的是最后一个row的最左边, 此时等于deepest说明我们之前来到过这个深度, 也是该深度左侧有node, 因此我们就不能更新ans.
时间复杂度: O(n)
空间复杂度: O(n)
