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

题目描述
给定一棵二叉树的根节点 root，请返回一个列表，其中每个元素是该树每一层的最大值。

示例：

输入：root = [1,3,2,5,3,null,9]
输出：[1,3,9]
解释：
          1
         / \
        3   2
       / \   \
      5   3   9
第0层最大值：1
第1层最大值：3
第2层最大值：9

解题过程
目标：逐层遍历树，记录每层的最大值。
关键：需要知道何时进入下一层，因此适合用广度优先搜索（BFS），逐层处理节点。

步骤分解

1. 初始化

   • 如果根节点为空，直接返回空列表。
   • 创建队列（存储当前层节点），先将根节点入队。
   • 创建结果列表 result。

2. 逐层处理

   • 只要队列不为空，说明还有层未处理：
     a. 获取当前层的节点数量 level_size（即队列当前长度）。
     b. 初始化当前层的最大值 level_max 为一个极小值（如 float('-inf')）。
     c. 循环 level_size 次，每次从队列取出一个节点：
     • 更新 level_max = max(level_max, 节点值)。
     • 如果该节点有左子节点，将左子节点入队。
     • 如果该节点有右子节点，将右子节点入队。
       d. 将 level_max 加入 result。

3. 返回结果

   • 遍历结束后，返回 result。

示例推演（以题目示例为例）

• 初始队列：[1]，result = []
• 第0层：
  • level_size = 1，level_max = -∞
  • 处理节点 1：level_max = max(-∞, 1) = 1，子节点 3、2 入队。
  • 结束循环，result = [1]
• 第1层：
  • 队列现在为 [3, 2]，level_size = 2，level_max = -∞
  • 处理节点 3：level_max = max(-∞, 3) = 3，子节点 5、3 入队。
  • 处理节点 2：level_max = max(3, 2) = 3，子节点 9 入队。
  • 结束循环，result = [1, 3]
• 第2层：
  • 队列现在为 [5, 3, 9]，level_size = 3，level_max = -∞
  • 依次处理节点：
    • 节点 5：level_max = 5
    • 节点 3：level_max = max(5, 3) = 5
    • 节点 9：level_max = max(5, 9) = 9
  • 结束循环，result = [1, 3, 9]
• 队列为空，返回 [1, 3, 9]

复杂度分析

• 时间复杂度：O(n)，每个节点访问一次。
• 空间复杂度：O(n)，队列最多存储一层节点，最坏情况为 O(n)。