leetcode解题: Find Bottom Left Tree Value (513)

发表于 | 分类于

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

Example 1:
Input:

1
2
3
  2
 / \
1   3

Output:
1
Example 2:
Input:

1
2
3
4
5
6
7
    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：DFS, O(N)

这题code写起来很简单，思路是这样的：每到一层第一个扫描到的可能就是我们要找的node。那么不断的更新这个node的值最后当遍历完这个树之后就可以得到答案了。
DFS遍历的时候维护一个全局变量maxdepth， 然后每下一层就更新一下当前的depth，如果depth比maxdepth大，说明当前到达的是一个新层，而且访问的一定是这一层的最左的元素。
Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    int val = 0;
    int maxDepth = 0;
    public int findBottomLeftValue(TreeNode root) {
        
        dfs(root, 1);
        return val;
    }
    
    void dfs(TreeNode root, int depth) {
        if (root == null) {
            return;
        }
        
        if (depth > maxDepth) {
            maxDepth = depth;
            val = root.val;
        }
        
        if (root.left != null) {
            dfs(root.left, depth + 1);
        }
        
        if (root.right != null) {
            dfs(root.right, depth + 1);
        }
    }
    
    
    
}