二叉树层序遍历实战：LeetCode 1161最大层内元素和全解析-北京尧图网络

这几天刷每日一题正好碰到LeetCode 1161这道“最大层内元素和”。题目本身不复杂属于二叉树里的基础题但我发现评论区里翻车的人不少——不是不会做而是在几个细节上栽了跟头。要么是返回的层号错了要么是没处理节点值为负数的情况要么干脆用int存层和差点溢出。这道题其实特别适合用来检验你对层序遍历BFS的掌握程度。它不考什么高深算法考的就是你对“按层处理”这个思路的熟练度以及处理边界条件的细心程度。我把我的解题思路、踩过的坑、以及几种不同写法都整理出来希望对正在刷题的朋友有帮助。不管你是刚接触二叉树的新手还是准备面试想巩固基础的老手这篇都能给你一些参考。1. 读懂题目的两个关键点求最大层而不是最大路径先别急着写代码把题意彻底搞清楚比什么都重要。1.1 “层内元素和”到底在求什么所谓“层内元素和”就是你得把二叉树同一层的所有节点值加起来然后比较每一层的和选出最大的那个返回它的层号。举个例子根节点在第1层它的两个子节点在第2层以此类推。这道题要求的不是路径和、不是最大节点值而是整棵树的每一层分别求和然后取最大值所在的层数。很多新手容易把这道题跟“二叉树的最大路径和”搞混。路径和是顺着某个方向把节点串起来求和层内元素和则是横向的、把同一水平线上的节点一起算。这两者在遍历方式上有本质区别路径和通常用DFS配合递归回溯层内元素和则天然适合BFS一层一层扫下去。想明白这一点你的解法方向就不会跑偏。1.2 题目里藏着的两个边界条件这道题有两个边界条件非常关键第一是层号从1开始计数根节点就是第1层返回值也是从1开始的层号。有些同学习惯用0开始计数最后忘记加1答案就少了一层。第二是如果存在多个层的内元素和相同且都是最大值要返回层号最小的那个。注意是“层号最小的”也就是说你不能随便找一个最大层就返回必须保证是最靠上的那一层。这两个条件单独看都很简单但合在一起会在你的实现里埋下不少坑后面我会详细说。另外还有一个容易忽略的隐性条件节点值可能为负数。我看有些题解在初始化最大值时直接写int maxSum 0如果整棵树所有层的内元素和都是负数这个0就会导致一层都更新不了最终返回的结果就是错误的。题目里节点值的范围包含负数所以这种初始化方式就是错的。2. 层序遍历方案设计为什么BFS是这道题的最优解明确题意之后解法的思路其实已经浮出水面了一层一层地遍历累加每一层的节点值动态比较得出最大值。2.1 BFS天然契合“按层处理”的需求BFS广度优先搜索用队列实现每次处理当前队列中的所有节点这批节点恰好就是同一层的全部节点。处理完这一批之后队列里剩下的就是下一层的全部节点。这种“批量处理”的特性让你在代码里可以非常自然地切分每一层然后对每一层单独求和、单独比较。如果用DFS深度优先搜索来做也不是不行但你需要额外维护一个“层号”参数把节点值累加到对应层的数组里遍历完整个树之后再统一比较。这样做明显绕了一步代码逻辑也不如BFS直观。所以对这道题来说BFS就是最优解它把“按层”这个需求直接映射到了遍历方式上。2.2 逐层累加与动态比较的完整流程整个算法的流程可以拆成四步初始化一个队列把根节点放进去当前层号记为1。记录当前队列的长度size这个size就是当前层的节点数量然后连续弹出size个节点弹出的过程中累加节点值同时把每个节点的左右子节点非空放入队列。这一层处理完后用累加得到的层和去跟当前最大层和比较如果严格大于就更新最大值和对应的层号。层号加1继续处理下一层直到队列为空。这里的第2步是BFS分层的关键技巧你必须在处理当前层之前把size记录下来因为如果你边弹出边加入子节点队列的长度会一直变化你就分不清哪些节点属于当前层、哪些属于下一层。先记录size然后只弹出size个节点就能保证这size个节点恰好是当前层的全部节点。动态比较的逻辑也值得琢磨你不需要先把所有层的和都算出来再统一比较而是每算完一层就和当前最大值比一次最终遍历结束后记录下来的那层就是答案。这种“边算边比”的做法节省了一个存储所有层和的数组空间上更省。我前面提到的“严格大于”条件对应题目要求的“返回层号最小的一个”。因为你的遍历顺序是从第1层往下走的所以如果某个层和等于当前最大值你什么都不做自然就保住了最早出现的那个最大值层号只有遇到更大的和才去更新答案。条件如果写成等值情况下会更新成更靠下的层那就错了。3. 代码落地细节溢出、初始化和层号计数三个容易翻车的点思路讲清楚了直接看代码。我平时用Java写题下面是这道题的一个标准BFS实现你可以直接照着写也可以改成你熟悉的语言class Solution { public int maxLevelSum(TreeNode root) { // 题目说了树不为空但防御性判断写上总没错 if (root null) { return 0; } QueueTreeNode queue new LinkedList(); queue.offer(root); int level 1; long maxSum Long.MIN_VALUE; int answer 1; while (!queue.isEmpty()) { int size queue.size(); long sum 0L; 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; answer level; } level; } return answer; } }3.1 这段代码里藏着的三个防坑设计第一个防坑设计是求和变量用long而不是int。我把这个放第一位是因为它最隐蔽。题目给的节点值范围是[-10^5, 10^5]节点数最多10^4理论上单层最大和大约是10^9这个量级int勉强能装下。但是这种“勉强够用”的代码我在实际开发中是不会写的因为你不知道测试用例会不会有个别极端情况也不知道题目会不会有变体。用long存储层和是零成本的保险长期刷题养成的习惯是凡是求和先想一下最坏情况超出int范围就换long不要等WA了再回头改。第二个防坑设计是最大值初始化为Long.MIN_VALUE而不是0。原因前面说过节点值可能全是负数。如果初始化为0那么所有层的和都是负数时maxSum永远不会被更新最终返回的层号就是初始化的1但第1层不一定真的是最大层。有些题解为了省事写int maxSum Integer.MIN_VALUE本身没错但如果层和是longmaxSum也得是long否则比较时会出现类型不匹配的问题。第三个防坑设计是层号level从1开始并且只在循环体内自增。对应题目层号从1开始计数的要求。每次进入while循环level代表的就是当前正在处理的层号处理完一层之后再自增。这个逻辑非常直白但确实有人在循环内外放错自增位置导致返回的结果始终差一层。3.2 如果换成Python和C要当心什么Python玩家在这道题上有个天然优势Python的int是不限长的不存在溢出问题所以求和变量直接用int就行。但Python写BFS的时候要注意用collections.deque来实现队列不要用list因为deque的popleft是O(1)而list的pop(0)是O(n)在大数据量下会有明显性能差距。C玩家最需要注意的是数据类型。int的范围是[-2^31, 2^31-1]前面算过这道题的极端层和可能接近10^9虽然int理论放得下但同样是“勉强够用”。稳妥起见直接用long long同时比较的变量也得是long long别一个int一个long long混着比编译器虽然会帮你做隐式转换但容易埋下隐患。还有一个所有语言都适用的细节遍历子节点时要把非空判断放在每一层的循环体里不要在入队的时候把null也放进去。如果你把null放进了队列后面弹出节点时还得再判断一次“当前层节点数量”就变得不干净了层的边界也会被null干扰。我见过有人把左右子节点无脑queue.offer(node.left)结果层数统计直接错乱排查了半天才发现是null节点混进了队列。4. 扩展解法与复杂度对比DFS也能解但有一个隐藏代价BFS是这道题的主流解法但不是说DFS就不能做。了解DFS的写法能让你在面试中展示对多种遍历方式的理解。4.1 DFS加数组累加的做法用DFS的思路也不难你从根节点开始递归每往下走一层深度加1走到节点时把节点值累加到对应深度的总和上。所有节点都遍历完后再遍历一遍累加结果找出最大和所在的深度。这个方案需要一个数组或哈希表来存储“深度 - 层和”的映射。因为树的总深度未知用ListLong更方便容量不够时动态扩容。伪代码如下class Solution { private ListLong levelSum new ArrayList(); public int maxLevelSum(TreeNode root) { dfs(root, 1); int answer 1; long maxSum Long.MIN_VALUE; for (int i 0; i levelSum.size(); i) { long sum levelSum.get(i); if (sum maxSum) { maxSum sum; answer i 1; // 索引0对应第1层 } } return answer; } private void dfs(TreeNode node, int depth) { if (node null) { return; } // 首次访问这一层时需要先补一个0占位 if (levelSum.size() depth) { levelSum.add(0L); } levelSum.set(depth - 1, levelSum.get(depth - 1) node.val); dfs(node.left, depth 1); dfs(node.right, depth 1); } }这段代码里有个细节if (levelSum.size() depth)这个判断不能省。因为DFS是先往左子树一路走到最深处再回头你第一次访问第5层的时候ArrayList的size很可能还是3如果不先添加占位元素后面用set(depth-1, ...)就会越界。这个判断就是用来处理“首次到达更深层”的情况。4.2 两种方案的复杂度对比从复杂度上看两个方案的时间都是O(n)因为每个节点都要访问一次但空间上有区别我整理了一个表方案时间复杂度空间复杂度适用场景BFS队列O(n)O(w)w是树的最大宽度最坏O(n)通用首选代码直观不会被递归深度坑DFS ListO(n)O(h) O(depth)h是树的高度适合展示多种思路不追求极致稳定DFS 显式栈O(n)O(h) O(depth)但无递归栈风险递归深度过深时的替代方案这里面我要特别提醒DFS递归的隐藏代价如果这棵树退化成一个链状结构高度达到10^4甚至10^5递归深度就会非常大。Java和C的递归栈都有限制深度太深会直接栈溢出。这道题的约束下可能还没问题但如果你在面试中主动写DFS面试官大概率会追问一句“如果树很深怎么办”这时候你要能答上来“可以改成显式栈迭代”。BFS就不存在这个隐患因为队列占用的空间只跟树的宽度有关跟高度无关。所以我的结论是DFS能解这道题但BFS在稳定性上更优。除非面试官明确要求“用递归实现”否则我推荐BFS。5. 从面试视角看这道题出题人真正在考什么LeetCode的每日一题并不都是“刷就完了”的题像1161这种题面试官是很喜欢拿来考人的因为它能用一道题同时考察好几个基础点。5.1 这道题考察的三个能力层级第一个能力层级是“会不会层序遍历”。能不能熟练写出BFS框架、能不能用size变量正确切分每一层这基本上是一道送分题但如果送分题都写不利索面试官对你的评价会大打折扣。我见过不少候选人说到二叉树遍历能说出“层序就是队列”真让写代码时却卡在“怎么知道一层结束了一共几个节点”这种问题上。第二个能力层级是“能不能处理边界条件”。这一考察点体现在细节里层号从1开始、多个最大值返回最小层号、节点值可能是负数导致不能用0当初始值、求和结果附近int边界——这些都是送命题。很多人主流程写得对挂在细节上。面试官不会直接告诉你“这里有坑”但你的代码一跑测试用例问题就暴露了。第三个能力层级是“能不能分析清楚复杂度”。面试官大概率会追问“你的方案时间复杂度和空间复杂度分别是多少有没有更优的解法”对于这道题O(n)的时间复杂度已经是最优了因为每个节点你都绕不开但你要能说清楚为什么O(n)是最优下界以及BFS的空间复杂度为什么是最坏O(n)。这些比代码本身更能体现算法功底。5.2 同类型变体题与应对套路二叉树“按层”系列是一个大家族1161只是其中一员。你把这题的套路吃透后顺手可以做做这些变体637题二叉树的层平均值同样是BFS按层处理每层求和后除以该层节点数。515题在每个树行中找最大值每层求最大逻辑几乎跟1161一样。199题二叉树的右视图每层只取最右边的节点BFS size切分就能解。429题 N叉树的层序遍历把左右子节点的处理改成遍历子节点列表。2415题反转二叉树的奇数层按层处理后针对奇数层做反转。这些题的共同套路就一句话用while循环控制层数在循环内先用size锁定当前层的节点数再统一处理这一层。你只要把这个框架记牢遇到任何“按层”的题都能套上去。我刷这类题刷到后面基本不用思考就能把框架写出来因为它们的结构高度一致。我个人在实际操作中的一个体会是做这类题时不要只求AC要试着用不同的写法各实现一遍。BFS写一遍DFS写一遍再想想如果不用队列只用数组能不能模拟。这种多角度练习比刷十道新题都管用。你能把一道简单的题吃透到“无论面试官怎么变形你都能应对”的程度那刷题的时间才算真正花在了刀刃上。最后分享一个小技巧这道题你用BFS写完通过后可以故意把sum maxSum改成sum maxSum再提交一次看看输出结果有什么变化。你就会直观地感受到“返回最小层号”这个约束在代码里是怎么体现的了。这种对比测试比自己单纯背结论印象深刻得多。

二叉树层序遍历实战：LeetCode 1161最大层内元素和全解析

相关推荐

SpringBoot考编论坛网站毕设全解析：从需求到部署实战

Cursor程序员的屠龙刀：用TaoToken统一Key打通AI工具链配置

AI内容合规实践指南：技术中立与法律边界

更多资讯

AI绘画提示词案例网站推荐

越南公司商业登记证书到底怎么看？跨境合作前这份科普请收好

OpenCV三维重建实战：法线估计与网格生成关键技术

Multisim 安装教程：装完提示「无法访问主数据库」，问题出在安装选项上

微信小程序护肤购物系统开发：从架构到二次开发全解析

Stable Diffusion 出图全链路：VAE、UNet、采样器与LoRA

今日更新

MATLAB+Yalmip+CPLEX实战：综合能源系统优化调度全流程解析

I3C比I2C快10倍？RK3576实战：速率、DTS配置与混合总线避坑指南

字符串转对象：JSON.parse、new Function与URLSearchParams

本周精选

如何彻底离线使用 Laya-CoreML：Hugging Face 下载、缓存机制与 local_files_only 详解

基于1Panel 部署MySQL MCP 服务：TaoToken 统一 Key 接入与 config.toml 配置实战

崇州园区营销网站建设避坑指南：5大注意事项保备案安全

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？