1. 题目拆解与思路底座1.1 题目本质从“全局最大”到“每层最大”LeetCode 515 这道题在很多刷题列表里被归为“二叉树层序遍历”题目本身也不绕给定一棵二叉树返回每一行也就是每一层节点里的最大值。这里的“行”不是文件里的行而是树的深度根节点在第 0 行它的直接子节点在第 1 行以此类推。最终输出的是一个数组数组下标对应深度数组元素是那一层所有节点的最大值。我第一次看到这道题时以为又是一个“求整棵树最大值”的变体后来仔细读题才发现多了“每个树行”这个限定词。这个限定词直接决定了算法套路不能只遍历一遍找全局最大而必须把节点按深度分组再逐组比较。换句话说这道题真正考的是“在遍历过程中如何感知当前节点属于哪一层”。用一个简单例子来看。假设有一棵这样的二叉树1 / \ 3 2 / \ \ 5 3 9它的层结构是这样的第 0 行只有根节点 1最大值是 1。第 1 行有节点 3 和 2最大值是 3。第 2 行有节点 5、3 和 9最大值是 9。所以答案应该是[1, 3, 9]。这棵树总共三行答案数组就有三个元素。这个一一对应的关系就是题目的核心约束。如果面试的时候只用“全局最大值”的思路想最多得到一个 9这在最简单的测试用例上就会出错。所以第一件事必须确定树的深度要和输出数组的下标绑定。把“每层”变成“每个深度”数据结构的问题就变成了一个带层号遍历的问题。1.2 为什么“按层”是关键词“按层”这两个字决定了你能选的遍历方式。树的遍历无非深度优先DFS和广度优先BFS两条路但它们在“分层”这件事上的天然匹配度完全不同。BFS 是天然按层推进的它用队列存储待访问节点队列里同一时间的节点基本都属于相邻层。只要在循环里控制每层节点的数量就能精确地把每一层“切”出来。DFS 是直接往深处走的它不会等一层扫完再进下一层而是沿着一条分支走到黑。想要按层统计就需要在递归参数里显式带上depth用这个深度值去对应结果数组的下标。所以这道题的两种主流解法本质上都围绕同一个关键字展开怎么把“当前节点在第几层”这个信息保留下来。BFS 用“当前层节点数”来卡边界DFS 用“递归深度”来对齐答案数组。两种做法都是在做同一件事——给节点贴上层的标签。这也是为什么这道题适合作为树的入门进阶题它不会像“验证二叉搜索树”那样有复杂的性质判断也不像“二叉树的最大深度”那样只需要一个整数它要求你同时关注“结构分层”和“层级聚合”。把这道题吃透后面做层序遍历的“右视图”“层平均值”“N叉树层序遍历”都会顺畅很多。2. BFS 层序遍历最直观的解法2.1 关键BFS 如何卡住“层”的边界BFS 的标准实现是用一个队列把根节点放进去然后循环弹出节点、处理节点、把子节点加入队列。如果只是这么做你确实能按“先来后到”的顺序访问所有节点但队列里会同时混着不同层的节点。比如根节点弹出后它的两个子节点进入队尾此时队列里是这一层的全部节点处理完它们之后队列里才轮到下一层的节点。因此每轮循环开始前先记录一下当前队列的长度size这个size就是当前层的节点数量。接下来的内层循环只处理size次每次从队头弹出节点。一轮结束后队列里剩下的刚好全是下一层节点。这样不需要往队列里塞None分隔符也不需要维护两个队列一个长度变量就够了。这里有个很容易忽略的细节size必须在进入内层循环之前固定下来。如果你写成for _ in range(len(q))而循环体里不断往队列尾部追加子节点len(q)会动态变化导致内层循环会多处理本来属于下一层的节点当前层的边界就断了。这个坑我见过很多次代码跑起来结果忽对忽错特别难受。2.2 Python 实现与逐行拆解from collections import deque from typing import List, Optional class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def largestValues(self, root: Optional[TreeNode]) - List[int]: if not root: return [] ans [] q deque([root]) while q: size len(q) level_max float(-inf) for _ in range(size): node q.popleft() level_max max(level_max, node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) ans.append(level_max) return ans逐行解释一下核心逻辑空树直接返回空列表。这个判断不能省否则后面q deque([root])会放进一个None下一行就要报错。ans是最终结果列表索引代表层数值代表该层最大值。q deque([root])使用deque而不是普通列表。普通列表的pop(0)是 O(n) 操作deque的popleft()是 O(1)在大数据量下有本质区别。size len(q)固定当前层的节点数。这一步是整个 BFS 按层切分的灵魂。level_max每次进入新一层时重置为负无穷。这里用float(-inf)是为了兼容节点值可能出现负数的情况。内层循环从队头弹出size个节点每个节点都比较一次最大值然后把它的非空子节点加入队尾。内层循环结束后当前层的最大值已经确定写入ans。很多人会问为什么不用0初始化level_max因为题目没有规定节点值非负。一旦树里有负数比如[-1, -2, -3]用 0 初始化会导致整层最大值变成 0直接出错。用float(-inf)是通用做法不容易被脏数据坑到。2.3 边界条件与常见坑做这道题时我踩过和见过的坑主要集中在以下几点空树返回什么应该返回[]不是[0]也不是[None]。空树没有层也没有最大值。单节点树返回[root.val]只包含一个元素。节点值非常大或非常小不要假设节点值在某个范围统一用float(-inf)或float(inf)做初始值。左右子树为空加入子节点前必须判断是否为空否则会把None塞进队列后续访问node.val直接报AttributeError。如果面试时用了带哨兵节点的写法比如在层尾插入None作为分隔符也不是不行但代码会更脆弱。因为你必须保证每一层结束时准确放入一个None一旦树中出现空子节点处理逻辑就很容易乱。用size控制循环次数是 LeetCode 官方题解也采用的标准做法可读性和稳定性都更好。3. DFS 深度优先换个姿势也能解3.1 用深度下标代替队列分层BFS 的解法足够直观但面试官经常会追问一句“能不能用 DFS 做” 这时候如果你只会 BFS就容易被问住。DFS 做这道题的关键是把“层”编码为递归参数。思路是这样的从根节点开始根节点的深度是 0。每向下走一层深度加 1。我们维护一个结果数组res让res[depth]表示深度depth这一层目前见过的最大值。递归过程中如果第一次到达某个深度就把当前节点值放入res[depth]如果之前已经到过这个深度就比较并更新最大值。这样写的好处是遍历顺序本身不重要。无论是前序、中序还是后序只要每次递归都带上当前深度最终都能把所有节点按深度归类并且每一层的最大值被逐步更新出来。3.2 递归实现与边界处理from typing import List, Optional class Solution: def largestValues(self, root: Optional[TreeNode]) - List[int]: res [] def dfs(node: Optional[TreeNode], depth: int) - None: if not node: return if depth len(res): res.append(node.val) else: res[depth] max(res[depth], node.val) dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 0) return res解释几个关键点depth len(res)的判断是用来处理“第一次到达这个深度”的。因为 DFS 不一定按层顺序推进第一次访问深度 3 时可能第 0、1、2 层都已经访问过了所以res的长度正好等于depth。此时应该直接把这个节点的值作为该层初始最大值。如果depth len(res)说明该层已经有记录了就执行max更新。每次递归先左后右其实对结果没有影响。即使先右后左也只是初始最大值的来源不同最终最大值都一样。空节点直接返回不需要额外处理。这是因为空节点不是层的一部分不应该影响结果。这个解法的简洁程度甚至比 BFS 还高但有一个隐藏问题当树特别深时递归会占用大量调用栈。Python 默认递归深度在 1000 左右如果树退化成一条链严格来说可能触发RecursionError。所以如果要处理超深树最好把递归改成显式栈迭代。显式栈的写法也不难栈里同时存节点和深度class Solution: def largestValues(self, root: Optional[TreeNode]) - List[int]: res [] stack [(root, 0)] if root else [] while stack: node, depth stack.pop() if depth len(res): res.append(node.val) else: res[depth] max(res[depth], node.val) if node.right: stack.append((node.right, depth 1)) if node.left: stack.append((node.left, depth 1)) return res注意这里压栈顺序因为栈是后进先出想让左节点先被处理就得先压右节点再压左节点。当然对这道题来说处理顺序没有任何影响所以压栈顺序不重要。3.3 两种解法怎么选用一个表格总结一下维度BFS 层序遍历DFS 深度优先分层方式每轮记录当前队列长度递归参数带深度是否需要额外标记不需要不需要空间复杂度最坏 O(W)W 为最大层节点数最坏 O(H)H 为树的高度实现难度简单直观递归写法更简洁但有递归深度风险实时输出可以一层一层输出需要先遍历完整棵树如果树是满二叉树BFS 的队列在最后一层可能同时存约 N/2 个节点空间开销不小DFS 的递归栈深度只有 logN。如果树是一条链BFS 队列最多只有 1 到 2 个节点DFS 递归栈却可能达到 N这时候 BFS 更稳妥。我个人的习惯是面试时先讲 BFS因为最容易让对方跟上思路然后补一句“DFS 也能做核心是带深度递归”然后直接写出 DFS。这样既展示了两种遍历方式的掌握程度也把话题引向了复杂度对比算是一个主动控场的加分项。4. 复杂度、变体与面试追问4.1 时间与空间复杂度都别背错时间复杂度方面无论 BFS 还是 DFS每个节点都会被访问一次每条边也会被访问一次。对于一个有 N 个节点的二叉树时间就是 O(N)。这已经是最优解了因为你至少要把每个节点的值看一遍才知道这一层谁最大。空间复杂度要分两部分看BFSq队列最多同时容纳一层的节点。对于满二叉树最后一层约 N/2 个节点所以最坏空间复杂度为 O(W)W 是最大层节点数上限是 O(N)。DFS递归写法使用系统调用栈栈深度等于树的高度 H最坏情况下退化成链表H N所以空间复杂度 O(H)上限也是 O(N)。这里要注意很多人只会回答“O(N)”但如果面试官继续问“BFS 和 DFS 的空间谁更差”就需要结合树的形态来说明。宽树 BFS 更耗空间高树 DFS 更耗空间这个结论比单纯背一个数字有价值得多。4.2 N 叉树、森林和“每层最小值”变体把二叉树换成 N 叉树BFS 的写法几乎不用改只是把“加入左右子节点”改成“加入所有 children”class Solution: def largestValues(self, root: Optional[Node]) - List[int]: if not root: return [] ans [] q deque([root]) while q: size len(q) level_max float(-inf) for _ in range(size): node q.popleft() level_max max(level_max, node.val) for child in node.children: if child: q.append(child) ans.append(level_max) return ans这几乎就是一个模板。以后做“N 叉树层序遍历”“每层平均值”“每层最小值”都可以直接套。还有一个变体是“森林”给你多个二叉树的根节点要求把所有树按相同深度放在一起求最大值。这时候最简单的做法是把多个根一起放进队列从深度 0 开始统一 BFS或者分别对每棵树求出按层最大值数组再逐层合并取最大值。后者更容易理解但前者代码更少。如果把“最大值”换成“最小值”“平均值”“节点个数”“层宽”逻辑完全相同只改level_max的更新方式。所以这一道题练好等于练会了一类“按层聚合”问题。4.3 面试官喜欢追问的几个切入点我在实际面试和模拟面试里遇到过几个高频追问追问一能不能用 O(1) 额外空间做这道题如果二叉树本身就是完全二叉树或者允许修改树结构理论上可以用 Morris 遍历做到 O(1) 空间。但 Morris 遍历主要用于中序遍历按层聚合信息时会很绕需要额外维护“当前层是谁”的状态。实际面试中更推荐直接说常规解法已经是 O(N) 时间下界空间上 O(H) 或 O(W) 属于可接受的代价如果一定要 O(1) 空间可以探讨 Morris 方案但实现复杂度和可读性都会显著下降。追问二DFS 递归能改成非递归吗能上面已经给了显式栈版本。面试官问这个通常是想确认你是否理解递归的本质就是栈。追问三如果树很大内存放不下怎么办这时候常规遍历模型就不适用了可能需要外部排序、分布式遍历甚至先用其他数据结构做剪枝。这属于系统设计层面的问题不在算法题的常规范围内但可以体现你的边界意识。追问四如果要求每一层返回最大的前 K 个值呢那就不能只维护一个变量了。每一层需要一个大小为 K 的堆内层遍历时不断向堆里插入最后把堆顶或堆内容输出。整体复杂度从 O(N) 变成 O(N log K)属于优先队列的典型用法。5. 调试心得与常见问题速查5.1 我踩过的几个真实坑第一个坑是level_max的初始值。我刚开始刷题时看到题目示例全是正整数就不假思索地用 0 初始化。结果自己构造了一个负数用例答案直接错得离谱。后来我把所有“求最大/最小”的题都养成了一个习惯最大值用负无穷初始化最小值用正无穷初始化永远不依赖题目给的取值区间。第二个坑是 BFS 的固定size。我早期写代码时习惯于这样写while q: for _ in range(len(q)): node q.popleft() ...在 Python 里range(len(q))在循环开始前会先计算一次len(q)所以这个写法其实是对的。问题出在如果你在循环体内又使用len(q)去判断或者加入子节点后没有限制就容易混乱。更安全的做法是老老实实写size len(q)然后for _ in range(size)这样逻辑一眼就能看懂。第三个坑是 DFS 的res访问越界。我刚开始写 DFS 时直接写成res[depth] max(res[depth], node.val)没有判断depth len(res)。当第一次访问到一个新深度时res[depth]还不存在直接报IndexError。这个错误提醒我递归里维护的“全局状态”和普通数组一样必须先确认下标存在。第四个坑是递归深度。本地测试一个 1500 层深的链状树时Python 直接抛了RecursionError。从那以后凡是树深度可能很大的题我都会先问清楚数据范围再决定是否改用迭代。5.2 常见问题与排查表现象可能原因解决办法输出结果比预期多一层内层循环没有固定 size在每轮循环前记录size len(q)答案里出现 0 而不是负数level_max用 0 初始化改为float(-inf)DFS 报数组越界忘记处理第一次到达某深度用if depth len(res)判断递归代码报 RecursionError树太深递归栈溢出改用显式栈或 BFS空树返回 [0]没有做空树判断返回空列表[]队列里出现 None 并报错没判断子节点是否为空加入队列前检查if node.left:单节点树返回空列表根节点被跳过检查循环逻辑是否先处理根节点这张表基本覆盖了我辅导别人刷题时遇到的所有问题。如果调试时发现异常不要急着打印整个树先按表格里的方向定位。5.3 测试用例设计技巧刷题不能只靠 LeetCode 自带的示例一定要自己构造边界用例。我一般会测这几类空树root None期望[]。单节点root TreeNode(5)期望[5]。全负数例如[-1, -2, -3, -4]期望每个负数层都能正确返回负数最大值。链状树每个节点只有右子树例如[1, None, 2, None, 3]期望[1, 2, 3]。满二叉树例如[1, 2, 3, 4, 5, 6, 7]期望[1, 3, 7]。极大值比如节点值里有2**31 - 1确保比较时不会溢出Python 不用考虑溢出但 C/Java 需要。我习惯在本地写一个build_tree辅助函数把 LeetCode 输入的层序数组还原成二叉树然后再跑largestValues。这样可以在提交前快速验证很多自定义用例。6. 从“层最大值”看更广义的树6.1 热词里的各种树到底在说什么最近搜“树”这个关键词能看到一大串名词B 树、B 树、红黑树、哈夫曼树、字典树、行为树、设备树、表达式树甚至连“宇树机器狗”这种产品名都会凑上来。这些“树”虽然都叫树但解决的问题完全不同。B 树 / B 树面向磁盘和数据库索引追求多路平衡。红黑树一种平衡二叉搜索树用于 map、set 等有序容器。字典树也叫 Trie用于前缀匹配。哈夫曼树用于编码压缩追求带权路径长度最小。行为树游戏 AI 或机器人决策中常用的控制结构。设备树硬件描述数据结构用于 Linux 系统描述设备信息。表达式树把算式解析成树形结构便于计算和求导。它们和 LeetCode 515 的共通点不在于“最大值”而在于“树的层次结构”。无论哪种树一旦你需要按层级统计、按深度聚合、按父子关系做覆盖用到的遍历和分层思想都和这道题一致。比如设备树里子节点属性覆盖父节点、B 树叶子节点按链表延伸、行为树按优先级执行子节点这些都能从“分层处理”的角度去理解。6.2 把“按层取极值”迁移到真实系统很多人觉得这道题只能拿来应付面试其实不是。我举几个真实场景第一个场景是调用链分析。一个分布式请求可以用树来表示每个节点是一次服务调用节点值是耗时。如果需要找出每一层调用里最慢的是哪个节点本质就是这道题的 BFS 版本。你只需要把“树的层”换成“调用深度”把“最大值”换成“耗时最大值”然后按层扫描即可。第二个场景是前端组件树性能分析。一个页面组件可以看成树每个组件有渲染耗时或节点数量。要找出最影响首屏渲染的那一层就需要逐层统计总耗时或最大耗时。这里的层就是组件嵌套深度和二叉树的行没有任何区别。第三个场景是组织架构的薪酬统计。公司组织架构是一棵树每个节点是员工节点值可以是薪酬。要查看每一级组织里薪酬最高的人也是同样的按层聚合。只要数据能被组织成树这类问题的解法就不会变。这也是我一直强调“套路”的原因不要把 LeetCode 题当作孤立的脑筋急转弯而是把它当作一类现实问题的抽象建模。515 抽象出来的东西就是“在层次结构上做分组聚合”这个能力在很多领域都会用到。6.3 刷题之外的扩展练习建议如果你刚做完 515我建议立刻做下面这几个题因为它们几乎是同一个模板LeetCode 199 二叉树的右视图每层取最右节点BFS 内层循环里判断是不是最后一个。LeetCode 637 二叉树的层平均值每层累加再除 size。LeetCode 429 N 叉树的层序遍历把左右孩子改成遍历 children。LeetCode 107 二叉树的层序遍历 II自底向上只需最后反转结果数组。剑指 Offer 32 - I 从上到下打印二叉树不带行号的简单 BFS。把这几个题连起来刷一遍你会发现 BFS 的骨架几乎不需要改动变的只是内层循环里的聚合逻辑。这就是刷题从“背代码”变成“理解模板”的关键一步。我个人在实际操作中的体会是515 最值得练的不是“会不会写”而是“能不能讲清楚为什么这样写”。如果你能在一个空白文档里从题意推导出 BFS 的size固定技巧再推导出 DFS 的深度下标思路那这题才算真正过关。面试时把过程讲给面试官听比默默写出答案要有说服力得多。