★ FEATURED ARTICLE LeetCode 1161 这道“最大层内元素和”是我某天刷每日一题时遇到的。第一眼看到它很多人都会觉得这题简单得不像每日一题——二叉树的层序遍历闭着眼睛就能写每层求个和保留最大值对应的层号收工。可等我真的提交了几次才发现题目里那些不容易注意的规则比如层号从 1 开始、全部层和都是负数时初始值该设成什么、最大值相同时返回最小层号任何一个踩中都会让你在 WA 和 AC 之间反复横跳。这篇文章我会先把题意拆透再把 BFS 和 DFS 两种写法都摆出来最后把我踩过的坑、排查思路和面试时可以主动聊的风向标都整理给你。适合正在刷二叉树基础题、准备面试手撕算法、或者想系统练 BFS/DFS 的同学。1. 题目到底在问什么先别急着写代码1.1 拆开“最大层内元素和”这个关键词“最大层内元素和”里的关键词其实是“层”和“和”。一棵二叉树的“层”是从根开始往下数的深度层次根是第 1 层这题的层号从 1 开始按层逐层递增。所谓“层内元素和”就是把同一层的所有节点值全部加在一起。题目最后要做的工作就是比较所有层的元素和找到最大值对应的那一层返回层号。这里要特别注意LeetCode 原题描述里写得很清楚如果有多层的元素和相同且都是最大返回最小的那个层号。这个规则不是可有可无的附加说明它直接决定了你在更新答案时用还是。第一次做这道题的人十有八九会忽略这个细节因为测试用例里出现平局的概率看起来不高但面试官很喜欢在你看完代码后补一句“如果最大和出现在两层该怎么办”所以解题前一定要先把这行规则刻在脑子里。题目给出的节点值范围是 [-10^5, 10^5]一棵树里的节点数量通常在 10^4 级别。即便所有节点都取最大值单层和也不过在 10^9 量级用 int 是装得下的。不过为了稳妥不少人会习惯性用 long 来做累加这属于一种防御性编程面试被问到也说得清楚。真正容易出问题的不是数值溢出而是最大值的初始值设置。1.2 手推两个示例两个例子把题目规则串起来先用 LeetCode 自带的第一个例子过一遍。输入是root [1,7,0,7,-8,null,null]这表示根节点是 1第二层有两个节点 7 和 0第三层有两个节点 7 和 -8因为节点 0 没有孩子。按层累加第 1 层和是 1第 2 层和是 7 0 7第 3 层和是 7 (-8) -1。最大值是 7出现在第 2 层所以答案输出 2。第二个例子是root [989,null,10250,98693,-89388,null,null,null,-32127]。这棵树长得比较奇怪根是 989右孩子是 1025010250 的左孩子是 98693、右孩子是 -8938898693 的右孩子是 -32127。逐层求第 1 层是 989第 2 层是 10250第 3 层是 98693 (-89388) 9305第 4 层是 -32127。最大是 10250所以还是返回第 2 层。这个例子的价值在于节点分布不是满二叉树每一层的节点数也不一样层内求和时必须老老实实把该层所有非空节点都算上null 不需要也不应该参与求和。1.3 边界约定空树、null 节点、负数全在的层如果把代码写成生产环境级别的风格空树这个边界值得提前想清楚。LeetCode 的测试数据里通常 root 不会为空但你写的方法如果能处理空输入就体现了代码的健壮性。返回什么因为没有“层”的概念很多 Java 题解里直接返回 0面试时如果你能主动说“我选择返回 0因为题目约定树非空实际工程里可以按业务需要改成抛异常或者返回 -1”这个细节反而会成为加分项。还有一类容易忽略的情况层内存在负数甚至所有层的和都是负数。比如一棵只有两个节点的树root [-5, -3]第 1 层和是 -5第 2 层和是 -3最大值是 -3答案应该返回 2。如果你把累加最大和的变量初始值设为 0第一层和 -5 永远不会大于 0答案就会停留在初始状态最终输出 1这个结果显然是错的。这就是我反复强调初始值必须设成Integer.MIN_VALUE或负无穷的原因。2. 解法选型BFS 和 DFS为什么我两个都讲2.1 BFS 逐层累加最贴合“层”的概念BFS 全称是广度优先搜索用队列一层一层地往下扫。做这道题时BFS 最大的优势不是快而是几乎不需要额外思维转换外层循环控制“当前层”内层循环把这一层的所有节点从队列里弹出来求和同时把它们的左右孩子加入队列供下一层使用。具体流程可以想象成一条流水线队列里初始只有 root。进入第一轮循环先记录当前队列长度 size这个 size 就是第 1 层的节点数。把 size 个节点全部取出val 累加进 sum再把每个节点的非空孩子放入队列。一轮结束后sum 就是第 1 层的和拿它和当前最大值比较更新答案层号。接下来进入第二轮队列里正好是第 2 层的所有节点size 就是第 2 层节点数。如此往复直到队列为空。这套逻辑其实对所有“按层处理”的问题都通用。比如二叉树的层序遍历、求最大宽度、连接右指针、按层输出节点等换了壳子核心都是“拿到本层长度循环弹出本层节点顺手入队下一层”。所以把这道题做透等于把一整个系列的层序遍历题都复习了一遍。2.2 BFS 的代码骨架和“层数计数器”设计实现 BFS 时通常会维护三个变量level表示当前处理到第几层初始值为 0每完成一轮循环自增 1maxSum存历史最大和初始值必须是极小值answer存历史最大和对应的层号。用 Java 写出来是这样class Solution { public int maxLevelSum(TreeNode root) { if (root null) return 0; QueueTreeNode queue new LinkedList(); queue.offer(root); int maxSum Integer.MIN_VALUE; int level 0; int ans 0; while (!queue.isEmpty()) { int size queue.size(); int sum 0; level; for (int i 0; i size; i) { TreeNode node queue.poll(); sum node.val; if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } if (sum maxSum) { maxSum sum; ans level; } } return ans; } }这个版本有几个刻意为之的点。level是在进入 while 循环后、还没开始遍历当前层之前自增的所以第一轮处理的是第 1 层如果写在 for 循环之后level 就会落后一层最后返回的答案要再加一非常容易把人绕晕。sum在每轮开始前重新置为 0保证它只累计当前层不被上一层的数据污染。空节点不需要特判因为入队前已经只收非空孩子这是层序遍历里最常见的写法。2.3 DFS 带深度累加不用队列换一种思考方式DFS 全称是深度优先搜索走的是“从根一直扎到叶子再回头”的路线。它和“层”这个概念天然有点不搭因为递归调用栈里不会天然区分层但我们可以给递归函数加一个depth参数从 root 开始depth1每向下一层depth1。这样一个节点被访问时它属于第 depth 层这件事就是完全确定的。用 DFS 做这道题的核心思路是不急着边遍历边比较而是先准备一个“层号和累积和”的映射表递归遍历整棵树每访问一个节点就把节点的值加到sums[depth]上。整棵树遍历完sums里就保存了每一层的总和最后再扫一遍找到最大值对应的最小层号即可。这种“先收集再比较”的思路和 BFS“边收集边比较”相比代码执行顺序不同但最终结果一致。我身边不少刚开始刷题的朋友总觉得 DFS 和 BFS 是对立的其实不对。它们是遍历一棵树的两种视角前者强调“一条路走到底”后者强调“同层兄弟挨个过”。遇到二叉树题目第一反应应该是判断哪种视角更适合当前的问题结构。这道题问的是“层”BFS 自然是直觉答案但如果题目改成“根到叶子路径上最长的和”DFS 反而就更顺手。两种思路都练熟才能在面试时灵活切换。2.4 DFS 参考实现和为什么建议你两种都要会用 Python 写 DFS 版本可以非常简短class Solution: def maxLevelSum(self, root: Optional[TreeNode]) - int: sums {} def dfs(node, depth): if not node: return sums[depth] sums.get(depth, 0) node.val dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 1) return min(sums, keylambda k: (-sums[k], k))这里的返回值用了很漂亮的 Python 技巧min(sums, keylambda k: (-sums[k], k))意思是按“和的相反数”升序、再按层号升序的规则取最小值。最大和对应的键会排在最前面如果出现平局就自动选择了更小的层号。这个写法在处理“取最大但要求最小索引”这类需求时很通用日常工作中也经常用到。那为什么我建议两种解法都要掌握因为面试的时候大多数人只会出一个 AC 结果但优秀的候选人会把复杂度的差别讲清楚。BFS 的队列最大长度取决于某一层的最大宽度DFS 的递归栈最大深度取决于树的高度。对一棵很宽却很矮的树BFS 更费空间对一棵很深但不宽的树DFS 的递归深度可能更吓人。能把两种思路都讲明白说明你不只是在背模板而是真的理解遍历的本质。3. 完整实现与踩坑记录从 WA 到 AC3.1 三种语言实现快速对比我习惯在本地用 C、Java、Python 各写一遍不是为了炫技而是为了让自己在不同语言思维下都能快速实现。这里把 C 版本也贴出来方便习惯 C 的读者直接抄作业class Solution { public: int maxLevelSum(TreeNode* root) { if (!root) return 0; queueTreeNode* q; q.push(root); int maxSum INT_MIN; int level 0; int ans 0; while (!q.empty()) { int size q.size(); int sum 0; level; while (size--) { TreeNode* node q.front(); q.pop(); sum node-val; if (node-left) q.push(node-left); if (node-right) q.push(node-right); } if (sum maxSum) { maxSum sum; ans level; } } return ans; } };三种语言放在一起对比逻辑完全一致只有容器和语法上的细微差异语言队列容器极小值写法空节点处理JavaQueueTreeNodeLinkedListInteger.MIN_VALUEnode.left ! null判断后入队CqueueTreeNode*INT_MIN用指针本身判空Python可以先 DFS 用字典或 BFS 用dequefloat(-inf)if not node我建议刷题时至少固定一种主语言把这道题写成肌肉记忆。换语言对算法理解帮助有限但能帮你分清“语言特性”和“算法思想”之间的边界。3.2 高频坑之一最大值初始值不是随便写的maxSum的初始值是最经典的错误。用 0 初始化是最常见的失误背后的原因也很好理解平时做的求和题目里最终答案通常都是非负数0 作为起点的惯性思维就带过来了。但在这道题里一旦所有层的和都是负数0 maxSum永远不成立最终答案会停留在初始状态返回错误的层号。正确的做法是Integer.MIN_VALUE、INT_MIN或float(-inf)也就是该语言能表示的最小值。有人会问能不能用-1000000000可以但没必要你还要额外确认这个数值比任何可能的层和都小。直接使用语言提供的极小值常量既不会溢出语义也清晰。3.3 高频坑之二层号起点和自增时机层号从 1 开始还是从 0 开始直接影响最后的答案。如果实现时depth从 0 开始计数那返回时必须加 1否则会差一层。在 BFS 版本里最容易出错的是level自增的位置。我之前帮一个朋友排查过代码他写的循环结构是while (!queue.isEmpty()) { int size queue.size(); int sum 0; for (int i 0; i size; i) { // ... } level; if (sum maxSum) { ... } }乍一看没问题每一层处理完再自增逻辑也是对的。但如果第一轮循环把level从 0 变成 1ans记录下来的是 1第二轮变成 2记录 2。前提是初始化level0最后返回的ans正好正确。问题出在很多变体写法里把level初始化为 1又在循环末尾自增结果第一层记成 2。排查这种问题最快的办法是在更新ans前打印level和sum拿一个只有两个节点的例子手推一遍马上就能发现差在哪一层。3.4 高频坑之三最大值相同到底返回哪一层这道题让我长了记性的第三个细节就是平局规则。LeetCode 要求返回“最小的层号”也就是离根最近的那一层。这个规则直接体现在比较符号上sum maxSum和sum maxSum的结果是不一样的。我举个例子假设第 2 层和第 5 层的和都是 10而 10 是全局最大。如果使用第 2 层先遇到maxSum从较小值变成 10ans2第 5 层再遇到时sum maxSum不满足严格大于ans不会被覆盖最终返回 2。如果使用第 5 层会把ans覆盖成 5最终返回 5两个结果只有一个正确。差别只有一个字符却直接影响 AC 与否。3.5 一次真实的调试过程我第一次做这题时用的是 Java BFS本地测试[1,7,0,7,-8,null,null]通过了一提交却报了错错误用例大概是[-5,-3]这一类。我一开始还很疑惑在纸上算了半天第 1 层 -5第 2 层 -3答案明明是 2为什么我的程序返回 1后来才发现是我的maxSum初始值为 0。第 1 层和是 -5-5 0不成立第 2 层和是 -3同样不成立。整个循环跑完ans还停留在初始值 1。这个调试过程虽然只花了五分钟但它给我的教训比看十篇题解都深刻求最大值的时候初始值必须设成最小可能值而不是你以为的“安全值”。后来我写代码前会先扫一眼数据范围估算一下结果可能落在什么区间再决定初始值用什么。4. 复杂度、变体与面试延伸4.1 时间与空间复杂度别只会说 O(N)设树中节点总数为 n。BFS 版本每个节点恰好入队、出队一次每个节点还需要常数时间处理左右孩子所以时间复杂度是 O(n)。空间上队列最多容纳某一层的全部节点最坏情况是一棵满二叉树的最底层节点数约 n/2所以空间复杂度是 O(n)。DFS 递归版本同样访问每个节点一次时间 O(n)空间取决于递归深度最坏情况是树退化成链深度也是 n空间 O(n)。面试时如果想把这个问题答得更出彩可以主动补一句这道题的时间复杂度存在理论下界你至少要访问一次所有节点才能知道每层和是多少所以 O(n) 已经是最优。这句话虽小但能体现你对问题边界有感知而不是只会背复杂度公式。4.2 变体一最大层平均值很多二叉树的层相关题目都是在“层和”上面加一层变化。比如把题目改成求“最大层内元素平均值”核心逻辑就变成每一步不仅要累计sum还要记录这一层的节点数量count最后比较的是sum / count。这里有个小坑平均值是浮点数比较时要注意精度的处理。力扣这类题通常会允许一个误差范围所以直接比较 double 一般没问题。但如果是在工程里我更建议用分数比较或者设定一个极小阈值1e-9避免浮点误差引发判断不一致。4.3 变体二多叉树与层和序列顺着 DFS 的思路往下走你会发现sums字典其实就是一个按层号为下标的数组。如果题目换成多叉树每个节点有多个孩子BFS 解法只需要把node.left和node.right的判断换成“遍历当前节点的所有孩子”即可DFS 解法同样只需要把递归里对左右孩子调用的位置改成对子节点列表循环。这种“把二叉树思路推广到多叉树”的能力在面试的 follow-up 环节经常被考察。再延伸一步如果想知道每一层和的完整序列而不是只返回最大层号BFS 里每次循环结束把sum存进一个列表就行DFS 里遍历完sums字典按层号排序输出即可。这个序列在后续处理里还可以做很多文章比如求连续层的最大和子段。4.4 面试被追问的三个问题该怎么接如果你在一面或者二面遇到了这题面试官大概率会在你写完代码后问这几个问题我建议提前组织好语言。第一个追问大概率是“为什么用 BFS 不用 DFS或者反过来”。你可以说因为题目按层组织BFS 天然能在遍历过程中逐层求和、逐层比较不需要额外的存储结构DFS 则需要一个字典先记录再扫描代码长一点但对树的高度更友好。没有标准答案关键是说出两种方案的利弊。第二个追问可能是“如果树的节点非常多内存有限怎么办”。这时候可以讨论 BFS 队列峰值和 DFS 调用栈深度的权衡甚至提到如果树存不下可以考虑流式读取节点并按层聚合。面试官想听的不是一个死答案而是你面对资源约束时的分析过程。第三个追问可能是“如果最大层有两个为什么返回最小的层号这个规则怎么落到代码里”。这个问题对应的是与的细节你还可以顺便给出一个构造平局用例的方法造一棵两层的树第一层和为 3第二层两个节点之和也为 3那么答案是 1。能现场构造出测试用例绝对是个加分动作。最后补一句我自己的习惯每次刷完这种“简单题”我都会把本题的 BFS 和 DFS 两种写法各提交一遍并且在本地把maxSum初始值、平局规则、空树分支三个位置故意改错观察报错现象。故意踩坑比看十篇题解记得都牢。你现在如果正在跟着每日一题打卡建议用这题练手的时候先把 1161 跑熟再去挑战后续更大的二叉树题目会有一种一通百通的顺畅感。
阅读完成 · 觉得有帮助？
