【LeetCode-中等题】513. 找树左下角的值

题目

方法一：前序递归

在递归遍历到叶子结点时，对比此时的节点深度，若当前节点深度大于当前最大深度，就更新value值，最后记录下的value即为最下最左的节点值

带值（深度）递归（纯递归）

class Solution {
    int Deep = -1;
    int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root,0);
        return value ;
    }
    public void dfs(TreeNode root,int depth){
        if(root == null) return;
        if(root.left == null &&root.right == null) {
            if(depth >Deep){
                Deep = depth;
                value = root.val;
            }
        }
        dfs(root.left,depth+1);
        dfs(root.right,depth+1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

不带值（深度）递归（递归+深度回溯）

class Solution {
    int Deep = -1;
    int value = 0;
    int depth = 0;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root);
        return value ;
    }
    public void dfs(TreeNode root){
        if(root == null) return;
        if(root.left == null &&root.right == null) {
            if(depth >Deep){
                Deep = depth;
                value = root.val;
            }
        }
        depth++;
        dfs(root.left);
        dfs(root.right);
        depth--;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法二：层序遍历

层序遍历 按照从右向左加入每层节点的值，这样每层取出节点的时候，最后记录的就是每一层最左的节点值，然后直到最后一层，记录下最后一层最左的值

 public int findBottomLeftValue(TreeNode root) {
        int res  = 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            res = root.val;
            if(root.right!=null) queue.offer(root.right);
            //按照从右向左加入每层节点的值，这样每层取出节点的时候，最后记录的就是每一层最左的节点值
            if(root.left!=null) queue.offer(root.left);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13