513 找树左下角的值

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

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

题解

我们直观上可以用层序遍历来解决该问题。同时递归也可以解决，但是要记录最大的深度，达到最大深度时就找最左边的值。

层序遍历

var findBottomLeftValue = function(root) {
    const queue = []
    //至少有一個結果，所以放root
    let result = root.val
    //這裏省略 if(!root) {return result}
    queue.push(root)

    while(queue.length) {
        const size = queue.length

        for(let i=0;i<size;i++) {
            const current = queue.shift()

            if(i === 0) {
                //每次都更新result值，直到最後一層就是結果
                result = current.val
            }
            if(current.left) {
                queue.push(current.left)
            }
            if(current.right) {
                queue.push(current.right)
            }
        }
    }
    return result
}

递归遍历

我们在递归的时候需要考虑最大深度，以及最左侧的值两个问题。

我们这个递归是不论哪种遍历的，因为先处理哪个节点不影响最后的结果。在写递归遍历的过程中一定要想好哪种遍历。

这题关键点在于要定义最大深度和最左节点在递归外侧。

var findBottomLeftValue = function(root) {
    var maxDepth = -1
    var result
    var findBottomLeftValueRecursive = function(root, depth) {
        if(root && !root.left && !root.right) {
            if(maxDepth < depth) {
                maxDepth = depth
                result = root
            }
            return
        }
        if(root.left){
            findBottomLeftValueRecursive(root.left, depth+1)
        }

        if(root.right) {
            findBottomLeftValueRecursive(root.right, depth+1)
        }
    }

    findBottomLeftValueRecursive(root, 1)

    return result.val
}