中等

问题描述

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例 1：

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

示例 2：

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

提示：

• 二叉树的节点个数的范围是 [0,104]
• -231 <= Node.val <= 231 - 1

广度优先搜索

使用广度优先搜索进行一次层次遍历，每次遍历层次时，记录当前层次的最大值 $max$，层次遍历结束后，将 $max$ 加入到结果中。

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

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

深度优先搜索

对树进行一次深度优先搜索并记录当前节点的层级 $level$，当答案数组中没有当前层级的最大值记录，则添加当前节点的值，若有当前层级的最大值记录，则比较更新最大值记录。

/**
 * 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 largestValues = function (root) {
  const ans = []
  if (!root) return ans
  const dfs = (node, level) => {
    if (!node) return
    if (ans[level] == null) ans.push(node.val)
    else ans[level] = Math.max(ans[level], node.val)
    dfs(node.left, level + 1)
    dfs(node.right, level + 1)
  }
  dfs(root, 0)
  return ans
}

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