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

题解 - BFS

题目描述中 [最底层 最左边] ，首先想到的就是层序遍历。因为层序遍历刚好是一层一层遍历的，其他遍历方式是按分支遍历的。

怎么确定是 [最底层 最左边] 的节点呢？
之前层次遍历的特点是 本层入队，本层的元素依次出队的同时下一层元素开始进队。每一层是从左到右依次入队了，所以最后一个入队和出队的一定是[最底层 最右边] 的元素。
所以如果每一层的入队顺序是从右往左依次入队，那么最后一个入队和出队的元素一定是 [最底层 最左边] 的节点。所以我们可以用一个元素来记录入队的节点，那么该元素的最终值就是 [最底层 最左边] 的节点值

var findBottomLeftValue = function(root) {
    //套入层序遍历模板,每层元素从右往左入队,记录每次的入队元素
    const queue = new Array();
    queue.push(root);
    let res = root.val;
    while(queue.length){
        let node = queue.shift();
        res = node.val;
        if(node.right)queue.push(node.right);
        if(node.left)queue.push(node.left);
        
    }
    return res;
};

题解- DFS

前序遍历，记录下当前的层数如果比之前的最大层数大并且为叶子节点的话存到结果中。说明是新一层的做左边的叶子节点。

var findBottomLeftValue = function(root) {
    let max=0, res;
    
    function dfs( root,  deep) {
        if (root == null) return ;
        if (deep > max) { 
            max = deep;
            res = root.val;//记录的是每一层的最左边的节点
        }
        dfs(root.left, deep + 1);
        dfs(root.right, deep + 1);
    }

    dfs(root, 1);
    return res;
};