513. 找树左下角的值 (opens new window)

1.深搜

使用全局最大高度maxheight控制底层最左节点值得更新。height>maxheight包含两层含义：

• 出现了层数更高的节点，需要更新
• maxheight=height保证相同层数节点只更新一次，而搜索顺序是先左子树然后右子树，因此更新时保证一定是那一层的最左节点。

class Solution {
    int resval=0;
    int maxheight=Integer.MIN_VALUE;
    public int findBottomLeftValue(TreeNode root) {
        dfs(root,0);
        return resval;
    }
    public void dfs(TreeNode root,int height){
        if(height>maxheight){
            maxheight=height;
            resval=root.val;
        }
        if(root.left!=null) dfs(root.left,height+1);
        if(root.right!=null) dfs(root.right,height+1);
    }
}

2.层序遍历

根据题意自然想到层序遍历。每层遍历时将最左节点更新为第一个出队列节点。

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Deque<TreeNode> deque=new LinkedList<>();
        deque.offerLast(root);
        TreeNode bottomleft=root;
        while(!deque.isEmpty()){
            int size=deque.size();
            for(int i=0;i<size;i++){
                if(i==0) bottomleft=deque.peekFirst();
                TreeNode node=deque.peekFirst();
                if(node.left!=null) deque.offerLast(node.left);
                if(node.right!=null) deque.offerLast(node.right);
                deque.pollFirst();
            }
        }
        return bottomleft.val;
    }
}