中等

问题描述

给定一个二叉树的 根节点 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

广度优先搜索

使用广度优先搜索进行一次层次遍历，每次用当前层的首个节点来更新 $ans$，层次遍历结束后，$ans$ 存储的是最后一层最靠左的节点。

/**
 * 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 queue = [root]
  let ans = root.val
  while (queue.length) {
    ans = queue[0].val
    const q = []
    for (let i = 0; i < queue.length; i++) {
      const node = queue[i]
      if (node.left) q.push(node.left)
      if (node.right) q.push(node.right)
    }
    queue = q
  }
  return ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

深度优先搜索

对树进行一次深度优先搜索，优先搜索左子树，首次搜索到更深的层级时，必然是该层级最左的节点，更新最深层级记录 $depth$ 和结果 $ans$。

/**
 * 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 depth = -1
  let ans = root.val
  const dfs = (node, level) => {
    if (level > depth) {
      depth = level
      ans = node.val
    }
    if (node.left) dfs(node.left, level + 1)
    if (node.right) dfs(node.right, level + 1)
  }
  dfs(root, 0)
  return ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$