【Day 16 】2021-05-25 - 513. 找树左下角的值

题目描述

入选理由

1. 可以通过这道题感受一下层次遍历。
2. 可以用 DFS 和 BFS 两种解法

题目描述

给定一个二叉树，在树的最后一行找到最左边的值。

示例 1:

输入:

    2
   / \
  1   3

输出:
1


示例 2:

输入:

        1
       / \
      2   3
     /   / \
    4   5   6
       /
      7

输出:
7

注意: 您可以假设树（即给定的根节点）不为 NULL。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-bottom-left-tree-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

解法一

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n) max层节点数

第一反应就是层序遍历每层的第一个，进行更新就行了

var findBottomLeftValue = function (root) {
    let queen = [root]
    let result = null
    while (queen.length) {
        let length = queen.length
        for (let i = 0; i < length; i++) {
            let curr = queen.shift()
            if (i === 0) result = curr.val
            if (curr.left) queen.push(curr.left)
            if (curr.right) queen.push(curr.right)
        }
    }
    return result
};

解法二

时间复杂度：O(n)

空间复杂度: O(n)

记录 maxDepth,depth>maxDepth 时 更新 maxDepth 值，即只有第一次进入这个层级的时候会记录。

var findBottomLeftValue = function (root) {
    let maxDepth = -1
    let result = null
    function dfs(root, depth = 0) {
        if (!root) return null
        depth++
        if (depth > maxDepth) {
            maxDepth = depth
            result = root.val
        }
        dfs(root.left, depth)
        dfs(root.right, depth)
    }
    dfs(root)
    return result
};

参考回答

• 官方题解
• 精选题解