LeetCode二叉树最底层最左边的值

剑指 Offer II 045. 二叉树最底层最左边的值

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

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

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

来源：LeetCode

利用深度优先搜索，每遍历一层就将高度加1。 另外还需要记录height的变化，用height记录当前遍历的节点的变化，需要和curHeight进行比较，令curHeight存储高度，一直是最大的，curVal记录相应节点值。 由于要找到最左侧的节点值，就需要先遍历左子树，再遍历右子树，这样对于同一层的节点来说，最左边的节点一定最先遍历，也就是会更改相应的curVal值，当右子树层数一样时，curVal不会发生改变。

class Solution {

    int curHeight;
    int curVal;

    public int findBottomLeftValue(TreeNode root) {
        curHeight=0;
        curVal=root.val;
        dfs(root,0);
        return curVal;
    }

    public void dfs(TreeNode root,int height){
        
        TreeNode node = root;
        height++;
        if(node==null){
            return;
        }
        
        dfs(node.left,height);
        
        dfs(node.right,height);
        if(height>curHeight){
            curHeight=height;
            curVal=node.val;
        }
    }
}

还有一种方法就是广度优先搜索，类似于队列，所以就需要将同一层的节点，先将最右侧的节点遍历（相当于放入队列），然后再从右向左遍历，这样最终遍历的就是得求的节点。

官方题解