二叉树层序遍历：LeetCode 515题解法与优化

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 result2.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 result3.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 result3.3 两种方法的比较方法时间复杂度空间复杂度适用场景BFSO(N)O(N)更直观适合面试DFSO(N)O(H)代码简洁H为树高4. 常见问题与调试技巧4.1 空树处理很多同学会忘记处理root为None的情况导致运行时错误。务必在函数开头添加if not root: return []4.2 初始化最大值在每层开始时max_val应该初始化为负无穷而非0因为树中可能有负值max_val float(-inf)4.3 边界条件测试建议测试以下特殊情况空树只有根节点的树完全左斜或右斜的树所有节点值相同的树包含负值的树5. 实际应用场景这类层级遍历问题在实际开发中有广泛的应用比如文件系统的目录树遍历组织架构图的层级分析游戏中的AI决策树处理网络路由表的层级查询掌握这类算法不仅能帮助通过技术面试更能提升解决实际工程问题的能力。建议在理解本题的基础上继续练习LeetCode上的其他树相关问题如102.二叉树的层序遍历、199.二叉树的右视图等形成系统的解题思维。