1. 问题背景与需求拆解

今天要讨论的是LeetCode第515题"在每个树行中找最大值"，这是一道典型的二叉树层序遍历变种问题。作为2023年LeetCode周赛430的题目之一，它在企业面试中的出现频率相当高，特别是在考察候选人对基础数据结构的掌握程度时。

这道题的核心要求是：给定一棵二叉树的根节点root，返回该二叉树每一层中的最大值组成的数组。举个例子，对于二叉树：

1 / \ 3 2 / \ \ 5 3 9

需要返回[1,3,9]，因为第一层最大值是1，第二层是3，第三层是9。

2. 算法设计思路解析

2.1 层序遍历基础框架

解决这类层级相关的问题，最直接的想法就是使用广度优先搜索(BFS)进行层序遍历。标准的BFS模板如下：

from collections import deque def levelOrder(root): if not root: return [] queue = deque([root]) result = [] while queue: level_size = len(queue) current_level = [] for _ in range(level_size): node = queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result

2.2 本题的变种处理

在标准层序遍历的基础上，我们需要做两个关键调整：

1. 不记录整层的节点值，而是跟踪当前层的最大值
2. 在每层遍历结束时，将最大值加入结果列表

2.3 时间复杂度分析

该算法的时间复杂度为O(N)，其中N是树中的节点数量。因为我们需要访问每个节点恰好一次。空间复杂度在最坏情况下也是O(N)，即当树是完全不平衡时（例如每个节点都只有左子节点）。

3. 代码实现与优化

3.1 Python标准实现

from collections import deque def largestValues(root): if not root: return [] queue = deque([root]) result = [] while queue: level_size = len(queue) max_val = float('-inf') for _ in range(level_size): node = queue.popleft() max_val = max(max_val, node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(max_val) return result

3.2 递归DFS解法

虽然BFS更直观，但DFS也可以解决这个问题。我们需要在递归时记录当前深度：

def largestValues(root): result = [] def dfs(node, depth): if not node: return if depth == len(result): result.append(node.val) else: result[depth] = max(result[depth], node.val) dfs(node.left, depth + 1) dfs(node.right, depth + 1) dfs(root, 0) return result

3.3 两种方法的比较

4. 常见问题与调试技巧

4.1 空树处理

很多同学会忘记处理root为None的情况，导致运行时错误。务必在函数开头添加：

if not root: return []

4.2 初始化最大值

在每层开始时，max_val应该初始化为负无穷而非0，因为树中可能有负值：

max_val = float('-inf')

4.3 边界条件测试

建议测试以下特殊情况：

1. 空树
2. 只有根节点的树
3. 完全左斜或右斜的树
4. 所有节点值相同的树
5. 包含负值的树

5. 实际应用场景

这类层级遍历问题在实际开发中有广泛的应用，比如：

• 文件系统的目录树遍历
• 组织架构图的层级分析
• 游戏中的AI决策树处理
• 网络路由表的层级查询

掌握这类算法不仅能帮助通过技术面试，更能提升解决实际工程问题的能力。建议在理解本题的基础上，继续练习LeetCode上的其他树相关问题，如102.二叉树的层序遍历、199.二叉树的右视图等，形成系统的解题思维。