1. 题目理解与BFS思路分析LeetCode 1161 这道题标题写得很直白最大层内元素和。第一眼看到 BFS 这个标签我基本就确定了解题路线——二叉树的层序遍历用队列逐层扫过去每层累加求和记录最大值出现的层号。这道题在 LeetCode 上属于中等偏简单的那一档非常适合用来巩固 BFS 的分层处理技巧尤其是刚学完二叉树遍历、想从 DFS 过渡到 BFS 的读者拿它练手再合适不过。1.1 题面在问什么层内元素和题目给一棵二叉树要求返回“元素和最大”的那一层的层号。注意几个关键词层号从 1 开始根节点就是第 1 层。元素和是整层所有节点值的代数和节点值有正有负。如果存在多个层的元素和并列最大返回层号最小的那一层。举个例子root [1, 7, 0, 7, -8, null, null]这棵树结构是1 / \ 7 0 / \ 7 -8第 1 层只有根节点和是1第 2 层有7和0和是7第 3 层有7和-8和是-1。三层里面最大的是第 2 层所以答案返回2。这个例子有个容易踩的细节如果把第 3 层的-8漏掉就会误以为第 3 层只有7然后把最大层算错。题目里的节点值允许为负意味着求和结果不能单纯按照“哪层节点多哪层就大”来猜必须老老实实逐层加完再比。1.2 为什么第一反应是 BFS看到“层内元素和”最直接的想法就是把每一层的节点单独拎出来算一遍。二叉树里能做到“一层一层拎出来”的遍历方式就是层序遍历也就是 BFS。BFS 的实现思路很自然用一个队列先把根节点放进去然后不断从队头弹出节点同时把它的左右孩子放到队尾。这样弹出顺序天然是按照层来推进的而且弹出的节点会自动按层分组。这里我习惯用一个生活类比BFS 就像坐电梯逐层扫楼每层从左到右把住户全访问一遍再上下一层DFS 则像走楼梯一条道走到黑走到没路了再退回岔路口。题目要按层统计电梯逻辑显然更贴合。BFS 分层还有一个隐藏优势每层之间的边界很清晰只要在每次循环开始时记录一下当前队列长度这个长度就是当前层节点的数量处理完这个数量就说明这一层结束了。这个“记录 size 再消费”的技巧是绝大多数 BFS 分层题的核心后面的实现里我会重点讲。1.3 DFS 也能做但不推荐当然DFS 并不是不能做。用递归或者显式栈去做深度优先遍历同时维护每个节点所在的深度每到一个节点就把值累加到对应深度的桶里最后再从桶里找出和最大的那个深度。思路没问题代码也能过。但不推荐的原因有两个。第一是逻辑绕。DFS 天然是往深处走的为了知道当前在第几层递归参数里必须多带一个depth或者用栈模拟时维护节点和深度的元组。对于一棵层数很深的树递归还有爆栈风险。而 BFS 的层号天生就跟着循环走不需要额外维护。第二是空间消耗。DFS 需要维护一个长度等于树高的数组或哈希表来存每一层的和。树高可能达到n退化成链表这样空间就是 O(n)BFS 虽然队列也可能达到 O(n)但大多数树结构下 BFS 的队列峰值是树的宽度两者在理论上界相同实际却更可控。既然 BFS 更符合直觉、代码更短自然选它。2. 核心细节BFS 层序遍历的完整拆解这道题的解题模板其实就是 BFS 分层遍历的通用写法。把每一行代码拆开看你会发现每个细节都有它存在的理由少了哪个都可能出 bug。2.1 队列初始化与判空BFS 需要借助队列。Java 里我一般用LinkedList来实现Queue接口原因很简单LinkedList允许存null而ArrayDeque不允许。虽然二叉树遍历时我们通常不会往队列里放null但万一想用null做层分隔符LinkedList会更灵活。入队和出队方法我强烈建议用offer()和poll()而不是add()和remove()。原因在于add()在队列满时会抛异常remove()在队列空时会抛异常而offer()和poll()分别返回false和null虽然在我们手写的 BFS 里几乎不会触达这些边界但用返回状态的方法始终更安全。判空这一步容易被忽略。题目虽然保证root非空但写成if (root null) return 0;是零成本防御。为什么返回0而不是1因为空树压根没有层返回任意非 0 层号都是错的按“不存在”处理返回 0 最合理。2.2 size快照锁定当前层的边界这是 BFS 分层三要素里的第一要素进入每层处理前先把当前队列长度拍个快照。int size queue.size();千万别写成for (int i 0; i queue.size(); i)因为循环体里会不断把子节点入队queue.size()会随着迭代变化原本只想处理本层节点结果可能把下一层的新节点也一并消费掉层边界直接崩掉。正确做法是在进入循环之前把当前层的节点数存到size变量里然后只从这个数量范围内弹节点。这个快照就是“当前层的节点清单”是 BFS 分层的锚点。这里顺便解释一个初学者常困惑的点为什么每层处理的次数是size而不是一直while (!queue.isEmpty())因为队列里既有当前层节点也有已经入队的下一层节点。要区分“现在正在处理哪一层”靠的就是这个快照。一直while循环会把所有层混在一次处理里求和当然就对不上号了。2.3 sum清零与层计数器每层开始前求和变量必须归零。我第一次写这道题的时候把sum定义在了while外层结果第一层的和累加了第二层第二层又累加了第三层最后答案完全错乱。这是一个看起来不起眼、实际非常致命的细节。正确逻辑是每进入一层sum 0;然后在该层内把所有节点值加进去处理完这一层后立刻拿sum和当前最大值比较比较完再进入下一层。注意sum清零的时机必须是在进入该层时而不是比较之后——如果你在比较完才清零下一层开始前已经带着上一层的数据了。层计数器level的递增位置也有讲究。它应该在外层while循环开始后、内层for循环之前level表示“我马上要处理第 level 层的节点”。这个顺序保证了第一个处理的层号是 1和题目要求一致。2.4 最大值的初始化与更新策略这里藏着一个经典的坑最大值初始值不能写0。因为节点值可能全为负数。比如树只有[-1, -2, -3]每层的和都是负数如果把maxSum初始化为0任何一层都不可能大于0最终答案永远是初始的层号而不是真正的最大层。正确初始化是Integer.MIN_VALUE在 C 里是INT_MINPython 里是float(-inf)。这样第一层比较时无论值多小都会被正确接收。更新策略同样有讲究题目要求“最大和相同返回最靠前的层”所以比较条件必须用不能用。if (sum maxSum) { maxSum sum; ans level; }如果用遇到并列最大值时会不断把ans更新成更靠后的层号最终返回的就是最大层的最深处和题意正好相反。这个细节题目里通常不会特别标红但测试用例一定会覆盖丢分丢得冤。3. 多语言实现一份思路三种写法同一个 BFS 思路在不同语言里写法略有差异但骨架完全一致。我把三种常用语言的版本都贴出来并标注每一步的作用方便你对照着理解也方便平时用自己熟悉的语言刷题。3.1 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 1; 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; } }这个版本里Queue接口 LinkedList的组合是最常见的 BFS 写法。offer/poll代替add/remove前面已经解释过原因。TreeNode是 LeetCode 内置的二叉树节点类包含val、left、right三个字段直接用即可。有个小细节ans初始化为1。因为题目至少有一层即使第一层的和是最小的比较后也会被正确更新为第一层。假如初始化成0当树只有一层时最后返回0就会出错。所以ans初始化为 1 是稳妥的配合maxSum MIN_VALUE第一层一定触发更新。3.2 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 1; while (!q.empty()) { int size q.size(); int sum 0; level; for (int i 0; i size; i) { 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; } };C 里注意q.front()只取队头元素但不会弹出需要单独q.pop()移除。这个两步操作经常有初学者漏掉pop导致死循环。另外if (node-left)这种写法可以直接判空比 Java 的! null更简洁原理是空指针隐式转换成false。INT_MIN来自climits头文件LeetCode 环境已经默认包含所以不用手动引入。如果用long long来存sum那maxSum类型也要同步改成long long注意类型一致性。3.3 Python 版本from collections import deque class Solution: def maxLevelSum(self, root: Optional[TreeNode]) - int: if not root: return 0 q deque([root]) max_sum float(-inf) level 0 ans 1 while q: size len(q) total 0 level 1 for _ in range(size): node q.popleft() total node.val if node.left: q.append(node.left) if node.right: q.append(node.right) if total max_sum: max_sum total ans level return ansPython 里deque的popleft()是 O(1)而列表pop(0)是 O(n)所以必须用deque。float(-inf)是 Python 表达负无穷的惯用方式用来初始化最大值。如果树节点值范围确定不超过10^9也可以直接用-10**18代替但-inf更通用、更语义化。三种语言对比下来你会发现核心逻辑完全一致差异只在语言自身的容器和语法细节上。说明 BFS 分层这个模式是语言无关的套路掌握了模板换语言只是照葫芦画瓢的事。4. 边界条件、溢出与性能分析一道题能 AC只是及格把边界情况想清楚才是写代码该有的状态。这题别看简单真要抠细节能抠出好几个容易忽略的点。4.1 空树与单节点题目默认root非空否则没法讨论层号。但工程习惯上仍然建议判空返回0表示“没有层”。单节点树的情况比较特殊只有一个根节点层号是1该层的和就是根节点值。即使这个值是-1000也正确返回1。这就是为什么maxSum不能用0初始化的意义所在。你可以手动跑一下代码里第一层sum -1000-1000 Integer.MIN_VALUE成立于是ans 1结果正确。如果把maxSum初始化成0这个用例直接返回错误的初始ans。所以遇到二叉树问题我习惯先问自己三个问题树能不能为空节点值可能为负吗层号从 0 还是 1 开始这三个问题的答案基本决定了初始化和边界判断怎么写。4.2 负值节点与和溢出负值节点是这道题专门设的坑前面反复提过。再补充一个点节点值范围是-10^5 Node.val 10^5二叉树节点数最多10^4那么任意一层的元素和最大不会超过10^9int类型完全装得下用Integer.MAX_VALUE和Integer.MIN_VALUE作为初始极值是安全的。但如果你在做同类题时发现节点值范围和节点数量可能突破int上限比如10^9 * 10^5就别硬撑了直接把sum和maxSum都声明成long。LeetCode 1161 里不需要但把这个意识培养起来是好事万一改个输入范围就不至于翻车。顺带说一句sum在每层结束后用来比较完全可以在判断完最大值之后不保留。因此每层重复使用同一个sum变量没有任何问题不需要额外开数组存每层的和。这正是 BFS 逐层处理的空间优势——DFS 想拿到层和要么开数组要么额外维护而 BFS 用一个临时变量就搞定。4.3 时间与空间复杂度时间复杂度是 O(n)其中 n 是二叉树节点总数。理由很直接每个节点恰好入队一次、出队一次入队出队都是 O(1)不存在重复访问。你可能注意到内层循环次数是size但所有size加起来恰好等于 n所以总时间仍是 O(n)。空间复杂度是 O(w)w 是树的最大宽度也就是队列中同时存在的最大节点数。最坏情况是一棵满二叉树最底层的叶子节点数约为 n/2所以空间复杂度上界是 O(n)。如果树退化成链表宽度为 1空间复杂度是 O(1)。和 DFS 的递归相比BFS 的空间消耗不随树的深度膨胀这是它处理深树时的可靠之处。5. 常见错误与调试心得这部分是我最想聊的。很多同学觉得这道题代码短随便写写就过了但真到面试白板编程时细节错误一个接一个。我把自己刷题时踩过和见过别人踩的坑整理成了一份速查表再做一点详细解释。5.1 常见问题速查表错误现象根本原因解决办法返回结果偏大或偏小层号不对sum没有每层清零每层while内、for前执行sum 0树全为负节点时结果恒为初始层号maxSum初始化为 0改为Integer.MIN_VALUE/INT_MIN/float(-inf)并列最大和时返回了更深层比较条件用了改用只允许更严格的最大值更新答案层号从 0 开始导致结果整体差 1没有在进入每层时先level在外层循环开始处递增层号保证首层为 1使用ArrayDeque存入null时报错ArrayDeque不允许 null改用LinkedList或不向队列中放入 null队列永远不为空程序死循环出队后忘记pop/poll先取队头再弹出确保能消费掉当前节点把下一层节点混进当前层处理for循环条件用了动态queue.size()循环前用int size queue.size()固定次数这个表里每条都是真实踩过的坑不是我凭空编的。尤其第一和第二条几乎每个初学 BFS 的人都会遇到至少一个。5.2 我个人踩过的坑讲一个我印象最深的失误最早的版本里我把sum定义在while循环外面然后想当然地以为“每层结束只要清零一次就行”。结果第一层累加完比较完最大值第二层开始前我确实清了零但清零点放在了maxSum比较之后。光看描述你可能觉得没问题实际上第二层开始时队列里除了第二层节点还残留着第一层所有子节点已经入队但因为我的清零点晚了一步内层for循环开始前sum还带着上一层的残留值。好在 LeetCode 的判题会明确告诉你错在哪个用例我看了测试样例[1, 7, 0, 7, -8, null, null]才明白是sum清零的位置不对。第二个坑是层号问题。一开始我天然认为和数组下标一样从 0 开始计层于是level写在了for循环后面结果返回的层号总是比预期小 1。后来我总结出一个习惯凡是题目里说“根节点是第 1 层”我就在外层while一开始先level这样进入内层循环时level正好表示当前处理的这层是哪一层清晰不容易错。第三个坑是关于ArrayDeque的。有段时间我特别喜欢用ArrayDeque当队列因为性能比LinkedList好。但在某道二叉树的层序遍历题里我往队列里放了null作为层分隔符直接抛出NullPointerException。从那时起我给自己定了一条规矩如果 BFS 里有放null的需求就老老实实用LinkedList没有放null的需求用ArrayDeque当然更高效。1161 这道题两种都能用因为我们在循环内通过node.left判空后才入队队列里不会出现null。6. 同类型题目与扩展思路1161 做完之后我不建议直接下一题。它的价值不在一道题本身而在于它把 BFS 分层模板的骨架完整呈现了一遍。这个模板可以迁移到很多 LeetCode 题目上花几分钟横向对比一下比闷头做十道新题还有用。6.1 对比最大宽度、最深层最左节点、右视图BFS 分层模板最常见的变体是while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { // 在这里根据题目需求做处理 } }拿几道经典题来对照LeetCode 662 二叉树最大宽度同样需要分层但每层不仅要拿到节点还要记录每个节点的位置索引宽度 最右索引 - 最左索引 1。模板不变额外维护索引。LeetCode 1302 层数最深叶子节点的和先 BFS 到最后一层再把最后一层的值加起来。实现上可以直接复用模板遍历完所有层后记录最后一层的sum。LeetCode 199 二叉树的右视图每层只取最右边的节点值也就是for循环里i size - 1时的节点。模板几乎原封不动。这几道题和 1161 放在一起看你会发现它们的内核完全一样通过 size 快照精准锁定每层的边界然后在边界内做文章。区别只在于每层内部要收集什么信息。把 1161 吃透再刷这几道题会顺畅很多。6.2 如果题目要求变了如果把题目改成“返回最大层内元素和的那一层的和而不是层号”代码只需改成最终返回maxSum其他逻辑完全不动。如果把“元素和”改成“平均值”也不难只要在每层循环结束时用sum除以size再参与比较即可。还有一种变体是如果元素和相同的层很多返回层号最大的那一层。这时候只需把比较条件从改成代码里一行改动就能满足。这提醒我们做题时一定要把题目里的“如果多个最大返回最小层号”这类限定读清楚它直接决定了那个看似不起眼的运算符是还是。6.3 用“每层求和”模板去刷题我自己的经验是BFS 分层题想稳定不失误最好把模板背到肌肉记忆的程度。所谓“分层三件套”就是外层while、内层for加 size 快照、每层结束后的业务逻辑。只要这三件套不乱代码基本不会偏离正确答案太远。最后分享一个小技巧遇到树相关的题目先在草稿纸上画一棵三层的简单树标出每一层的节点然后手动模拟 BFS 的入队出队过程。只要你能把“当前层有几个节点、下一层有哪些节点”这层关系搞清楚代码怎么写都不会错。我在带新人刷题时经常让他们这么做效果比直接看题解好得多。
LeetCode 1161 最大层内元素和：BFS层序遍历模板详解
1. 题目理解与BFS思路分析LeetCode 1161 这道题标题写得很直白最大层内元素和。第一眼看到 BFS 这个标签我基本就确定了解题路线——二叉树的层序遍历用队列逐层扫过去每层累加求和记录最大值出现的层号。这道题在 LeetCode 上属于中等偏简单的那一档非常适合用来巩固 BFS 的分层处理技巧尤其是刚学完二叉树遍历、想从 DFS 过渡到 BFS 的读者拿它练手再合适不过。1.1 题面在问什么层内元素和题目给一棵二叉树要求返回“元素和最大”的那一层的层号。注意几个关键词层号从 1 开始根节点就是第 1 层。元素和是整层所有节点值的代数和节点值有正有负。如果存在多个层的元素和并列最大返回层号最小的那一层。举个例子root [1, 7, 0, 7, -8, null, null]这棵树结构是1 / \ 7 0 / \ 7 -8第 1 层只有根节点和是1第 2 层有7和0和是7第 3 层有7和-8和是-1。三层里面最大的是第 2 层所以答案返回2。这个例子有个容易踩的细节如果把第 3 层的-8漏掉就会误以为第 3 层只有7然后把最大层算错。题目里的节点值允许为负意味着求和结果不能单纯按照“哪层节点多哪层就大”来猜必须老老实实逐层加完再比。1.2 为什么第一反应是 BFS看到“层内元素和”最直接的想法就是把每一层的节点单独拎出来算一遍。二叉树里能做到“一层一层拎出来”的遍历方式就是层序遍历也就是 BFS。BFS 的实现思路很自然用一个队列先把根节点放进去然后不断从队头弹出节点同时把它的左右孩子放到队尾。这样弹出顺序天然是按照层来推进的而且弹出的节点会自动按层分组。这里我习惯用一个生活类比BFS 就像坐电梯逐层扫楼每层从左到右把住户全访问一遍再上下一层DFS 则像走楼梯一条道走到黑走到没路了再退回岔路口。题目要按层统计电梯逻辑显然更贴合。BFS 分层还有一个隐藏优势每层之间的边界很清晰只要在每次循环开始时记录一下当前队列长度这个长度就是当前层节点的数量处理完这个数量就说明这一层结束了。这个“记录 size 再消费”的技巧是绝大多数 BFS 分层题的核心后面的实现里我会重点讲。1.3 DFS 也能做但不推荐当然DFS 并不是不能做。用递归或者显式栈去做深度优先遍历同时维护每个节点所在的深度每到一个节点就把值累加到对应深度的桶里最后再从桶里找出和最大的那个深度。思路没问题代码也能过。但不推荐的原因有两个。第一是逻辑绕。DFS 天然是往深处走的为了知道当前在第几层递归参数里必须多带一个depth或者用栈模拟时维护节点和深度的元组。对于一棵层数很深的树递归还有爆栈风险。而 BFS 的层号天生就跟着循环走不需要额外维护。第二是空间消耗。DFS 需要维护一个长度等于树高的数组或哈希表来存每一层的和。树高可能达到n退化成链表这样空间就是 O(n)BFS 虽然队列也可能达到 O(n)但大多数树结构下 BFS 的队列峰值是树的宽度两者在理论上界相同实际却更可控。既然 BFS 更符合直觉、代码更短自然选它。2. 核心细节BFS 层序遍历的完整拆解这道题的解题模板其实就是 BFS 分层遍历的通用写法。把每一行代码拆开看你会发现每个细节都有它存在的理由少了哪个都可能出 bug。2.1 队列初始化与判空BFS 需要借助队列。Java 里我一般用LinkedList来实现Queue接口原因很简单LinkedList允许存null而ArrayDeque不允许。虽然二叉树遍历时我们通常不会往队列里放null但万一想用null做层分隔符LinkedList会更灵活。入队和出队方法我强烈建议用offer()和poll()而不是add()和remove()。原因在于add()在队列满时会抛异常remove()在队列空时会抛异常而offer()和poll()分别返回false和null虽然在我们手写的 BFS 里几乎不会触达这些边界但用返回状态的方法始终更安全。判空这一步容易被忽略。题目虽然保证root非空但写成if (root null) return 0;是零成本防御。为什么返回0而不是1因为空树压根没有层返回任意非 0 层号都是错的按“不存在”处理返回 0 最合理。2.2 size快照锁定当前层的边界这是 BFS 分层三要素里的第一要素进入每层处理前先把当前队列长度拍个快照。int size queue.size();千万别写成for (int i 0; i queue.size(); i)因为循环体里会不断把子节点入队queue.size()会随着迭代变化原本只想处理本层节点结果可能把下一层的新节点也一并消费掉层边界直接崩掉。正确做法是在进入循环之前把当前层的节点数存到size变量里然后只从这个数量范围内弹节点。这个快照就是“当前层的节点清单”是 BFS 分层的锚点。这里顺便解释一个初学者常困惑的点为什么每层处理的次数是size而不是一直while (!queue.isEmpty())因为队列里既有当前层节点也有已经入队的下一层节点。要区分“现在正在处理哪一层”靠的就是这个快照。一直while循环会把所有层混在一次处理里求和当然就对不上号了。2.3 sum清零与层计数器每层开始前求和变量必须归零。我第一次写这道题的时候把sum定义在了while外层结果第一层的和累加了第二层第二层又累加了第三层最后答案完全错乱。这是一个看起来不起眼、实际非常致命的细节。正确逻辑是每进入一层sum 0;然后在该层内把所有节点值加进去处理完这一层后立刻拿sum和当前最大值比较比较完再进入下一层。注意sum清零的时机必须是在进入该层时而不是比较之后——如果你在比较完才清零下一层开始前已经带着上一层的数据了。层计数器level的递增位置也有讲究。它应该在外层while循环开始后、内层for循环之前level表示“我马上要处理第 level 层的节点”。这个顺序保证了第一个处理的层号是 1和题目要求一致。2.4 最大值的初始化与更新策略这里藏着一个经典的坑最大值初始值不能写0。因为节点值可能全为负数。比如树只有[-1, -2, -3]每层的和都是负数如果把maxSum初始化为0任何一层都不可能大于0最终答案永远是初始的层号而不是真正的最大层。正确初始化是Integer.MIN_VALUE在 C 里是INT_MINPython 里是float(-inf)。这样第一层比较时无论值多小都会被正确接收。更新策略同样有讲究题目要求“最大和相同返回最靠前的层”所以比较条件必须用不能用。if (sum maxSum) { maxSum sum; ans level; }如果用遇到并列最大值时会不断把ans更新成更靠后的层号最终返回的就是最大层的最深处和题意正好相反。这个细节题目里通常不会特别标红但测试用例一定会覆盖丢分丢得冤。3. 多语言实现一份思路三种写法同一个 BFS 思路在不同语言里写法略有差异但骨架完全一致。我把三种常用语言的版本都贴出来并标注每一步的作用方便你对照着理解也方便平时用自己熟悉的语言刷题。3.1 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 1; 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; } }这个版本里Queue接口 LinkedList的组合是最常见的 BFS 写法。offer/poll代替add/remove前面已经解释过原因。TreeNode是 LeetCode 内置的二叉树节点类包含val、left、right三个字段直接用即可。有个小细节ans初始化为1。因为题目至少有一层即使第一层的和是最小的比较后也会被正确更新为第一层。假如初始化成0当树只有一层时最后返回0就会出错。所以ans初始化为 1 是稳妥的配合maxSum MIN_VALUE第一层一定触发更新。3.2 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 1; while (!q.empty()) { int size q.size(); int sum 0; level; for (int i 0; i size; i) { 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; } };C 里注意q.front()只取队头元素但不会弹出需要单独q.pop()移除。这个两步操作经常有初学者漏掉pop导致死循环。另外if (node-left)这种写法可以直接判空比 Java 的! null更简洁原理是空指针隐式转换成false。INT_MIN来自climits头文件LeetCode 环境已经默认包含所以不用手动引入。如果用long long来存sum那maxSum类型也要同步改成long long注意类型一致性。3.3 Python 版本from collections import deque class Solution: def maxLevelSum(self, root: Optional[TreeNode]) - int: if not root: return 0 q deque([root]) max_sum float(-inf) level 0 ans 1 while q: size len(q) total 0 level 1 for _ in range(size): node q.popleft() total node.val if node.left: q.append(node.left) if node.right: q.append(node.right) if total max_sum: max_sum total ans level return ansPython 里deque的popleft()是 O(1)而列表pop(0)是 O(n)所以必须用deque。float(-inf)是 Python 表达负无穷的惯用方式用来初始化最大值。如果树节点值范围确定不超过10^9也可以直接用-10**18代替但-inf更通用、更语义化。三种语言对比下来你会发现核心逻辑完全一致差异只在语言自身的容器和语法细节上。说明 BFS 分层这个模式是语言无关的套路掌握了模板换语言只是照葫芦画瓢的事。4. 边界条件、溢出与性能分析一道题能 AC只是及格把边界情况想清楚才是写代码该有的状态。这题别看简单真要抠细节能抠出好几个容易忽略的点。4.1 空树与单节点题目默认root非空否则没法讨论层号。但工程习惯上仍然建议判空返回0表示“没有层”。单节点树的情况比较特殊只有一个根节点层号是1该层的和就是根节点值。即使这个值是-1000也正确返回1。这就是为什么maxSum不能用0初始化的意义所在。你可以手动跑一下代码里第一层sum -1000-1000 Integer.MIN_VALUE成立于是ans 1结果正确。如果把maxSum初始化成0这个用例直接返回错误的初始ans。所以遇到二叉树问题我习惯先问自己三个问题树能不能为空节点值可能为负吗层号从 0 还是 1 开始这三个问题的答案基本决定了初始化和边界判断怎么写。4.2 负值节点与和溢出负值节点是这道题专门设的坑前面反复提过。再补充一个点节点值范围是-10^5 Node.val 10^5二叉树节点数最多10^4那么任意一层的元素和最大不会超过10^9int类型完全装得下用Integer.MAX_VALUE和Integer.MIN_VALUE作为初始极值是安全的。但如果你在做同类题时发现节点值范围和节点数量可能突破int上限比如10^9 * 10^5就别硬撑了直接把sum和maxSum都声明成long。LeetCode 1161 里不需要但把这个意识培养起来是好事万一改个输入范围就不至于翻车。顺带说一句sum在每层结束后用来比较完全可以在判断完最大值之后不保留。因此每层重复使用同一个sum变量没有任何问题不需要额外开数组存每层的和。这正是 BFS 逐层处理的空间优势——DFS 想拿到层和要么开数组要么额外维护而 BFS 用一个临时变量就搞定。4.3 时间与空间复杂度时间复杂度是 O(n)其中 n 是二叉树节点总数。理由很直接每个节点恰好入队一次、出队一次入队出队都是 O(1)不存在重复访问。你可能注意到内层循环次数是size但所有size加起来恰好等于 n所以总时间仍是 O(n)。空间复杂度是 O(w)w 是树的最大宽度也就是队列中同时存在的最大节点数。最坏情况是一棵满二叉树最底层的叶子节点数约为 n/2所以空间复杂度上界是 O(n)。如果树退化成链表宽度为 1空间复杂度是 O(1)。和 DFS 的递归相比BFS 的空间消耗不随树的深度膨胀这是它处理深树时的可靠之处。5. 常见错误与调试心得这部分是我最想聊的。很多同学觉得这道题代码短随便写写就过了但真到面试白板编程时细节错误一个接一个。我把自己刷题时踩过和见过别人踩的坑整理成了一份速查表再做一点详细解释。5.1 常见问题速查表错误现象根本原因解决办法返回结果偏大或偏小层号不对sum没有每层清零每层while内、for前执行sum 0树全为负节点时结果恒为初始层号maxSum初始化为 0改为Integer.MIN_VALUE/INT_MIN/float(-inf)并列最大和时返回了更深层比较条件用了改用只允许更严格的最大值更新答案层号从 0 开始导致结果整体差 1没有在进入每层时先level在外层循环开始处递增层号保证首层为 1使用ArrayDeque存入null时报错ArrayDeque不允许 null改用LinkedList或不向队列中放入 null队列永远不为空程序死循环出队后忘记pop/poll先取队头再弹出确保能消费掉当前节点把下一层节点混进当前层处理for循环条件用了动态queue.size()循环前用int size queue.size()固定次数这个表里每条都是真实踩过的坑不是我凭空编的。尤其第一和第二条几乎每个初学 BFS 的人都会遇到至少一个。5.2 我个人踩过的坑讲一个我印象最深的失误最早的版本里我把sum定义在while循环外面然后想当然地以为“每层结束只要清零一次就行”。结果第一层累加完比较完最大值第二层开始前我确实清了零但清零点放在了maxSum比较之后。光看描述你可能觉得没问题实际上第二层开始时队列里除了第二层节点还残留着第一层所有子节点已经入队但因为我的清零点晚了一步内层for循环开始前sum还带着上一层的残留值。好在 LeetCode 的判题会明确告诉你错在哪个用例我看了测试样例[1, 7, 0, 7, -8, null, null]才明白是sum清零的位置不对。第二个坑是层号问题。一开始我天然认为和数组下标一样从 0 开始计层于是level写在了for循环后面结果返回的层号总是比预期小 1。后来我总结出一个习惯凡是题目里说“根节点是第 1 层”我就在外层while一开始先level这样进入内层循环时level正好表示当前处理的这层是哪一层清晰不容易错。第三个坑是关于ArrayDeque的。有段时间我特别喜欢用ArrayDeque当队列因为性能比LinkedList好。但在某道二叉树的层序遍历题里我往队列里放了null作为层分隔符直接抛出NullPointerException。从那时起我给自己定了一条规矩如果 BFS 里有放null的需求就老老实实用LinkedList没有放null的需求用ArrayDeque当然更高效。1161 这道题两种都能用因为我们在循环内通过node.left判空后才入队队列里不会出现null。6. 同类型题目与扩展思路1161 做完之后我不建议直接下一题。它的价值不在一道题本身而在于它把 BFS 分层模板的骨架完整呈现了一遍。这个模板可以迁移到很多 LeetCode 题目上花几分钟横向对比一下比闷头做十道新题还有用。6.1 对比最大宽度、最深层最左节点、右视图BFS 分层模板最常见的变体是while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { // 在这里根据题目需求做处理 } }拿几道经典题来对照LeetCode 662 二叉树最大宽度同样需要分层但每层不仅要拿到节点还要记录每个节点的位置索引宽度 最右索引 - 最左索引 1。模板不变额外维护索引。LeetCode 1302 层数最深叶子节点的和先 BFS 到最后一层再把最后一层的值加起来。实现上可以直接复用模板遍历完所有层后记录最后一层的sum。LeetCode 199 二叉树的右视图每层只取最右边的节点值也就是for循环里i size - 1时的节点。模板几乎原封不动。这几道题和 1161 放在一起看你会发现它们的内核完全一样通过 size 快照精准锁定每层的边界然后在边界内做文章。区别只在于每层内部要收集什么信息。把 1161 吃透再刷这几道题会顺畅很多。6.2 如果题目要求变了如果把题目改成“返回最大层内元素和的那一层的和而不是层号”代码只需改成最终返回maxSum其他逻辑完全不动。如果把“元素和”改成“平均值”也不难只要在每层循环结束时用sum除以size再参与比较即可。还有一种变体是如果元素和相同的层很多返回层号最大的那一层。这时候只需把比较条件从改成代码里一行改动就能满足。这提醒我们做题时一定要把题目里的“如果多个最大返回最小层号”这类限定读清楚它直接决定了那个看似不起眼的运算符是还是。6.3 用“每层求和”模板去刷题我自己的经验是BFS 分层题想稳定不失误最好把模板背到肌肉记忆的程度。所谓“分层三件套”就是外层while、内层for加 size 快照、每层结束后的业务逻辑。只要这三件套不乱代码基本不会偏离正确答案太远。最后分享一个小技巧遇到树相关的题目先在草稿纸上画一棵三层的简单树标出每一层的节点然后手动模拟 BFS 的入队出队过程。只要你能把“当前层有几个节点、下一层有哪些节点”这层关系搞清楚代码怎么写都不会错。我在带新人刷题时经常让他们这么做效果比直接看题解好得多。