LeetCode-513-找树左下角的值

一：题目描述：

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

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

二：示例与提示

示例 1:

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

示例 2:

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

提示:

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

三：思路

`广度优先搜索`

使用层序遍历，遍历每一层，最后一层的第一元素即是最左下角的元素

`深度优先搜索`

使用curDepth记录下每个节点当前的深度，来查找最大深度的节点
因为先遍历左节点后遍历右节点，所以在同层下一定是左节点先被遍历到。
即找最大深度的节点即是最左下角的节点

四：代码

`广度优先搜索`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    //层序遍历
    let res = []
    let queue = [root]
    while(queue.length){
        let length = queue.length
        const curLevel = []
        for(let i = 0; i < length; i++){
            let node = queue.shift()
            curLevel.push(node.val)
            if(node.left) queue.push(node.left)
            if(node.right) queue.push(node.right)
        }
        res.push(curLevel)
    }
    return res[res.length-1][0]
};

`深度优先搜索`

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var findBottomLeftValue = function(root) {
    //递归 找到最大深度的叶子节点
    let maxDepth = 0
    let res = null
    const dfsTree = (root, curPath) => {
        //找叶子节点
        if(!root.left && !root.right){
            //找最大叶子节点并更新
            if(curPath > maxDepth){
                maxDepth = curPath
                res = root.val
            }
        }
        //左右
        root.left && dfsTree(root.left, curPath + 1)
        root.right && dfsTree(root.right, curPath + 1)
    }
    dfsTree(root, 1)
    return res
};