515.在每个树行中找最大值.md

515.在每个树行中找最大值

/*
 * @lc app=leetcode.cn id=515 lang=typescript
 *
 * [515] 在每个树行中找最大值
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function largestValues(root: TreeNode | null): number[] {}
// @lc code=end

解法 1: bfs

• 时间复杂度:
• 空间复杂度:

function largestValues(root: TreeNode | null): number[] {
  if (!root) return []

  const res: number[] = []
  const bfs = (nodes: TreeNode[]) => {
    if (!nodes.length) return

    let max = -Infinity
    const tmp: TreeNode[] = []
    for (const node of nodes) {
      max = Math.max(max, node.val)
      tmp.push(...[node.left!, node.right!].filter(Boolean))
    }
    res.push(max)
    bfs(tmp)
  }
  bfs([root])
  return res
}

解法 2: dfs

• 时间复杂度:
• 空间复杂度:

function largestValues(root: TreeNode | null): number[] {
  if (!root) return []
  const res: number[] = []
  const dfs = (node: TreeNode, i = 0) => {
    res[i] = Math.max(res[i] ?? -Infinity, node.val)
    for (let child of [node.left, node.right].filter(Boolean)) {
      dfs(child!, i + 1)
    }
  }
  dfs(root)
  return res
}

Case

test.each([
  { input: { root: [1, 3, 2, 5, 3, null, 9] }, output: [1, 3, 9] },
  { input: { root: [1, 2, 3] }, output: [1, 3] },
  { input: { root: [1] }, output: [1] },
  { input: { root: [1, null, 2] }, output: [1, 2] },
  { input: { root: [] }, output: [] },
])('input: root = $input.root', ({ input: { root }, output }) => {
  expect(largestValues(BinaryTree.deserialize(root))).toEqual(output)
})