找树左下角的值

题目

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

• 二叉树的节点个数的范围是 [1, 10⁴], 即保证二叉树不为空.
• -2³¹ <= Node.val <= 2³¹ - 1

示例

输入:

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

输出: 7

题解

JavaScript - 深度优先遍历

每次优先 DFS 当前节点的左子树, 每次第一次搜索到当前深度 depth 时, 必然是当前深度的最左节点, 此时用当前节点值来更新 res.

/**
 * 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 = 0

  const dfs = (root, depth) => {
    if (!root) return

    if (depth > maxDepth) {
      maxDepth = depth
      res = root.val
    }

    dfs(root.left, depth + 1)
    dfs(root.right, depth + 1)
  }

  dfs(root, 1)
  return res
}

时间复杂度: O(n), 其中 n 是二叉树的节点数目.

空间复杂度: O(n), 最坏情况下退化成链, 递归深度为 n.

JavaScript - 广度优先遍历

使用广度优先搜索遍历每一层的节点. 在遍历一个节点时, 需要先把它的非空右子节点放入队列, 然后再把它的非空左子节点放入队列, 这样才能保证从右到左遍历每一层的节点. 广度优先搜索所遍历的最后一个节点的值就是最底层最左边节点的值.

/**
 * 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) {
  const queue = [root]
  let res = 0

  while (queue.length > 0) {
    const n = queue.length
    const level = []

    for (let i = 0; i < n; i++) {
      const node = queue.shift()

      if (node.right) queue.push(node.right)
      if (node.left) queue.push(node.left)

      res = node.val
    }
  }

  return res
}

时间复杂度: O(n), 其中 n 是二叉树的节点数目.

空间复杂度: O(n). 如果二叉树是满完全二叉树, 那么队列 queue 最多保存 n / 2 个节点