README.md

找树左下角的值

难度：中等

https://leetcode.cn/problems/find-bottom-left-tree-value/

题目

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

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

示例

示例 1:

输入: root = [2,1,3]
输出: 1

示例 2:

输入: [1,2,3,4,null,5,6,null,null,7]
输出: 7

解题

深度优先遍历

/**
 * 深度优先遍历
 * @desc 时间复杂度 O(N) 空间复杂度 O(N)
 * @param root
 * @returns
 */
export function findBottomLeftValue(root: TreeNode | null): number {
  let maxHeight = 0
  let ans = 0
  dfs(root, 0)

  return ans

  function dfs(node: TreeNode | null, height: number) {
    if (!node) return

    height++
    dfs(node.left, height)
    dfs(node.right, height)
    if (height > maxHeight) {
      maxHeight = height
      ans = node.val
    }
  }
}

广度优先遍历

/**
 * 广度优先遍历
 * @desc 时间复杂度 O(N) 空间复杂度 O(N)
 * @param root
 * @returns
 */
export function findBottomLeftValue2(root: TreeNode | null): number {
  if (!root) return -1

  let ans = 0
  const queue: TreeNode[] = [root]
  while (queue.length) {
    const node = queue.pop()!
    node.right && queue.unshift(node.right)
    node.left && queue.unshift(node.left)
    ans = node.val
  }

  return ans
}