【基础篇 - Day 16】 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)

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

var findBottomLeftValue = function (root) {
    let queue = [root]
    let first = ''
    while (queue.length) {
        let length = queue.length
        first = queue[0].val
        while (length--) {
            let curr = queue.shift()
            if (curr.left) queue.push(curr.left)
            if (curr.right) queue.push(curr.right)
        }
    }
    return first
};

解法二

时间复杂度：O(n)

空间复杂度: O(n)

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

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

https://github.com/leetcode-pp/91alg-2/issues/41#issuecomment-727715566

参考回答

• 官方题解 (opens new window)
• 精选题解 (opens new window)