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

题目描述
给你一棵二叉树的根节点 root，请找出该二叉树中每一层的最大值，并以数组形式返回。

例如，输入：root = [1,3,2,5,3,null,9]，对应的二叉树结构为：

        1
       / \
      3   2
     / \   \
    5   3   9

输出：[1,3,9]，因为第0层最大值是1，第1层最大值是3，第2层最大值是9。

题目要求：时间复杂度应尽量低，且需适应节点数最多可达 10^4 的规模。

解题思路
这个问题需要逐层遍历二叉树（即层序遍历），并在每一层中动态找出节点值的最大值，然后保存下来。由于是“逐层”处理，BFS（广度优先搜索）是自然的选择，因为它能按层依次访问节点。我们也可以使用DFS，但需要记录每个节点所在的层数，并在遍历过程中不断更新各层的最大值。

方法1：BFS（广度优先搜索）
BFS通过队列实现，每次处理一层，步骤如下：

1. 初始化：创建一个队列（例如 queue），将根节点入队（如果根节点非空）。
2. 逐层遍历：
   • 在每一层开始时，先获取当前队列中的节点数，这个数量就是当前层的节点总数。
   • 初始化一个变量 levelMax 为当前层的第一个节点的值（或者设为非常小的数，如负无穷）。
   • 依次从队列中取出当前层的每个节点，并更新 levelMax 为当前节点值与 levelMax 的较大者。
   • 将当前节点的左子节点和右子节点（如果存在）加入队列，供下一层处理。
   • 当前层所有节点处理完后，将 levelMax 加入结果列表。
3. 重复步骤2，直到队列为空。
4. 返回结果列表。

这种方法的时间复杂度是 O(N)，其中 N 是节点数，因为每个节点恰好入队出队一次。空间复杂度在最坏情况下（完全二叉树底层节点最多）为 O(N)。

方法2：DFS（深度优先搜索）
DFS 通过递归或栈实现，我们这里用递归，需要记录每个节点所在层数，并维护一个数组或列表来保存每层的最大值：

1. 定义一个列表 levelMaxValues 用于存储结果，在DFS过程中，如果访问到的层数 depth 等于 levelMaxValues 的长度，说明是第一次访问该层，直接将当前节点值加入列表；否则，更新 levelMaxValues[depth] 为当前节点值与列表中该层现有值的较大者。
2. 从根节点开始递归，初始深度为0。
3. 递归访问左子树和右子树，深度加1。
4. 遍历结束后，levelMaxValues 即为所求。

DFS的时间复杂度也是 O(N)，空间复杂度取决于递归栈的深度，在最坏情况下（树退化为链表）为 O(N)。

两种方法对比

• BFS 更直观，符合“逐层”的概念，代码易于理解和实现。
• DFS 递归写法简洁，但需要额外维护层数信息。在处理极大深度树时，递归可能导致栈溢出，此时可用迭代DFS（显式栈）替代。

考虑到清晰性和通用性，通常推荐使用 BFS 解决此题。

总结
本题考察二叉树遍历的基本功，重点在于如何按层处理节点并动态计算最大值。掌握 BFS 和 DFS 两种方法，能帮助你在不同场景下灵活选择。实践中，BFS 是这类“层相关”问题的首选。