找树左下角的值

513.找树左下角的值

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

提示:

• 二叉树的节点个数的范围是 [1,104]
• -231 <= Node.val <= 231 - 1

迭代法（层次遍历）

记录每一层最左结点的值，最后一层的最左节点几位数左下角的结点

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        if(root==null) return 0;
        int ans = 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            int size = que.size();
            for(int i = 0 ; i<size ;i++){
                TreeNode node = que.poll();
                if(i==0) ans = node.val; //记录每一层的第一个元素
                if(node.left!=null) que.offer(node.left);
                if(node.right!=null) que.offer(node.right);
            }
        }
        return ans;
    }

}

递归法（前序遍历）

记录最大化深度，前序遍历每一层遇到的第一个节点必定是最左节点

class Solution {
    int max_deep = -1; //记录最大的深度
    int value = 0;
    public int findBottomLeftValue(TreeNode root) {
        find_traversal(root, 0);
        return value;
    }

    //递归法
    public void find_traversal(TreeNode root , int deep){
        if(root==null) return;
        if(root.left==null && root.right==null){ //最左节点一定是叶子节点
            if(deep > max_deep){  //前序遍历，每一层第一个最先遇到的必然是左结点
                value = root.val;
                max_deep = deep;
            }
        }
        //deep+1隐含了回溯，每次返回deep都是原来的状态
        if(root.left != null) find_traversal(root.left, deep+1); 
        if(root.right != null)  find_traversal(root.right, deep+1);
    }
}