1. 题目拆解先理解最大层内元素和到底在问什么1.1 从二叉树层号说起力扣第1161题的全称是最大层内元素和英文是 Maximum Level Sum of a Binary Tree。它给你一棵二叉树的根节点 root要求你找到元素和最大的那一层并返回该层的层号。这里有个容易忽略的细节层号从1开始也就是根节点所在层是第一层不是从0开始。很多人在这种基础定义上翻车代码里把层号从0计数最后输出结果总差1。题目本身不复杂属于二叉树遍历的经典应用。但它有一个很有意思的点题目要求如果多个层的元素和相等返回层号最小的那一层。这个限制看似简单实际上暗藏玄机后面我专门讲。适合的读者主要是两类一类是刚开始刷二叉树、想用层序遍历练手的同学另一类是已经会写BFS/DFS但想搞清楚边界条件和细节优化的进阶选手。1.2 示例手动推演跟手算一样简单拿题目自带的示例来说假设二叉树长这样1 / \ 7 0 / \ \ 7 -8 9第一层只有根节点1和是1。第二层是7和0和是7。第三层是7、-8、9和是8。三个层比较下来最大的和是8对应第三层所以返回3。这个例子有个特别值得品的地方第三层虽然有负数-8但因为7和9足够大整体和仍然最大。这提醒我们绝不能因为某一层出现了负数就提前跳过它。还有人容易在计算第三层时漏掉右子树的9——注意节点0的右孩子是9它是存在的在遍历时如果只判断左孩子不为空、右孩子为空就停直接漏掉这一层的数据。再看一个修改后的例子如果第三层是7、-8没有9那么三层和分别是1、7、-1最大是7在第二层返回2。这说明最大层和不一定出现在最深层也不一定出现在靠近根的位置。唯一靠谱的做法就是老老实实把所有层都算一遍然后比较。1.3 题目约束里的隐藏信息题目给定的二叉树节点数范围通常是 1 到 10^4节点值范围可能是 -10^5 到 10^5。这意味着两件事第一节点值存在负数求和时初始值不能用0去硬比较最大值。如果你把maxSum初始化为0遇到所有层和都是负数的情况最终结果就会错误地停留在0导致返回的层号不对。正确做法是用一个足够小的数比如int最小值-2147483648或者直接用第一层的和作为初始值。第二节点数最多1万层数最多可能有一万。如果是一个链状二叉树每层只有一个节点。这种极端情况下BFS队列长度峰值也就是1DFS递归深度可能达到1万某些语言的递归栈可能会爆。所以DFS的递归写法在力扣上能过但如果你实在不放心可以用显式栈或改成BFS。2. BFS层序遍历解法最直观的逐层扫描2.1 队列为什么是层序遍历的标配说到二叉树按层来访问几乎所有人都会第一时间想到BFS广度优先搜索。BFS天然就是一层一层扩展开的用先进先出的队列承载这种顺序非常自然。每次从队列头部弹出一个节点就把它当成当前层的成员来处理处理完当前节点后再把它的左右孩子放入队列尾部这些孩子属于下一层。这里有一个老生常谈但必须强调的点BFS访问的顺序并不是层内从左到右这么简单队列中会有不同层的节点混在一起。所以必须通过某种方式区分当前层和下一层的界限。最常见的有两种方式一种是在每一轮遍历前先记录当前队列的长度size然后只循环size次这size个节点就是当前层另一种是使用两个队列轮换或者用特殊标记节点隔开。力扣题解里绝大多用第一种因为它简洁且不容易出错。2.2 确定层边界for循环的正确用法我在LeetCode上见过不少同学写BFS时踩过同一个坑在while (!queue.isEmpty())循环里直接来了一个for (TreeNode node : queue)或者干脆for (int i 0; i queue.size(); i)然后里面不断入队。注意queue.size()在循环中会动态变化你一边往队尾添加新节点一边用变化后的size作为循环次数逻辑就全乱了当前层会混入下一层的节点。正确做法是先把当前层的节点数固定下来int size queue.size(); 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); }用一个临时变量size把当前层节点数“冻结”住后续对队列的操作就不影响这一轮循环的次数。这是层序遍历里最核心的一行代码没有之一。Python写法类似可以用for _ in range(len(queue))但也要注意len(queue)是在进入循环前求值一次所以同样没问题。2.3 累加、比较、更新三个动作的顺序每一层的处理流程可以拆成三步先把这一层的所有节点值累加得到sum然后把sum和当前最大值maxSum比较如果sum更大就更新maxSum和答案层号ansLevel。你可能会觉得这个顺序理所当然但实际写代码时有个小陷阱很多人把maxSum的初始化值设置成Integer.MIN_VALUE后第一层比较会直接更新但此时层号可能没初始化好或者忘了记录第一层。更稳的做法是在进入循环之前不初始化maxSum而是在第一次有层的时候直接赋值。但这样代码分支会多一些。我自己的习惯是maxSum Integer.MIN_VALUE然后每层算完直接比较因为第一层的和无论多大、多小都会大于Integer.MIN_VALUE所以第一层必然会被记录。这其实利用了“最小值”的哨兵作用很安全。注意这里的ansLevel更新条件必须严格是sum maxSum而不是sum maxSum。为什么因为题目要求“如果多个层和相等返回层号最小者”。我们层序遍历本来就是从上到下的第一次遇到最大值时层号就是最小的。如果之后遇到一个和相同的层用会把层号覆盖成更大的那个那就错了。所以保持同层和出现时不更新答案自然就是最小的层号。这里我顺手给一个完整的Java版BFS实现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, ansLevel 0; while (!queue.isEmpty()) { level; int size queue.size(); int sum 0; 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; ansLevel level; } } return ansLevel; } }这个代码的时间复杂度是O(n)每个节点恰好访问一次空间复杂度是O(w)w是树的最大宽度也就是同一层最多节点数。在极端情况下比如完全二叉树最后一层节点数约为n/2空间复杂度就是O(n)。3. DFS递归解法不用队列也能统计每层和3.1 递归函数设计把层号传进参数BFS虽然直观但有些同学更习惯用递归思考问题。DFS深度优先搜索同样能解决这道题而且实现起来有一种“内存里维护每层和”的味道。核心思路是遍历每个节点时我们知道它属于第几层然后把这个节点值加到对应层的累计和里。递归函数的设计很简单void dfs(TreeNode* node, int depth, vectorlong long levelSum) { if (node nullptr) return; if (levelSum.size() depth) { levelSum.push_back(0); } levelSum[depth - 1] node-val; dfs(node-left, depth 1, levelSum); dfs(node-right, depth 1, levelSum); }这里levelSum是一个变长数组下标对应“层号减一”。当访问到一个新深度时如果数组长度不够就先扩展一格并初始化为0。这样无论二叉树长成什么样所有层的和都会按层号顺序放在数组里。3.2 用数组存每层和规避顺序问题BFS是一层一层计算所以比较最大值是“边算边比”不需要保存每一层完整结果。但DFS是跳着访问的比如深度优先会一路冲到底再把另一条分支拉起来所以访问顺序不代表层顺序。此时你必须先把所有层的和算完最后再遍历这个数组找出最大值和对应层号。算完之后找最大值也有讲究。因为要找“最小的层号”你可以从下标0开始遍历只有当当前值严格大于已有最大值时才更新下标。这样即使后面有相同的值你也不会覆盖前面的答案。和BFS里的逻辑如出一辙。这个解法的时间复杂度同样是O(n)空间复杂度平均O(log n)也就是递归栈的深度。但最坏情况下二叉树退化成链表递归深度达到n栈空间O(n)。力扣的测试数据一般不会让一万层的递归爆栈但如果你用Python写递归遇到比较深的树时可能会触发RecursionError可以设置sys.setrecursionlimit()或者干脆改用BFS。3.3 递归与迭代的取舍DFS递归写起来很清爽代码量最少。但如果你面试时被要求写这题我建议先给出BFS版本因为面试官听到“最大层内”第一反应通常就是层序遍历。BFS的迭代写法不依赖系统栈也不会有爆栈风险可解释性也更强。不过DFS版本也有它的价值它展示了“遍历顺序和统计逻辑解耦”的思路这在很多树形DP里面都是基础功夫。比如统计每层节点个数、每层最大最小值、每层平均值DFS同样可以套用levelSum数组的模式。所以两种解法都值得写一遍不要只背一个。下面补一个Python的DFS实现做对照class Solution: def maxLevelSum(self, root: Optional[TreeNode]) - int: level_sum [] def dfs(node: Optional[TreeNode], depth: int) - None: if not node: return if len(level_sum) depth: level_sum.append(0) level_sum[depth - 1] node.val dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 1) max_sum float(-inf) ans 0 for i, s in enumerate(level_sum): if s max_sum: max_sum s ans i 1 return ans4. 进阶负数节点、最小层号、溢出与性能优化4.1 层和为负数时初始值别再乱设成0我在前文已经提到maxSum的初始化很关键。用一个实际例子感受一下如果二叉树只有一个根节点值就是 -5那么唯一一层的和是 -5正确答案是1。但如果你把maxSum初始化为0比较-5 0不成立ansLevel永远停留在初始值0最后返回0就错了。力扣的判题器可不管你逻辑是不是“看起来差不多”结果错就是错。为什么很多人会把初始值写成0因为在整数求最大值的场景里0是一个“安全中性”的数比如“求数组里最大的正数”时0很好用。但这题节点值可以为负所以必须引入负无穷或者第一层和。负无穷在不同语言里的写法我列在下面语言写法JavaInteger.MIN_VALUECINT_MINPythonfloat(-inf)Gomath.MinInt32(或math.MinInt64)JavaScript-Infinity用float(-inf)在Python里与整数比较完全没问题因为Python的int和float可以比较大小。C里注意INT_MIN是在climits中定义。Go语言用math.MinInt需要看版本旧版本没有这个常量可以直接写-1 31。4.2 多个层和相同返回最上层还是最下层题目明确说了返回层号最小的那一层。这其实是降低了难度因为如果你用BFS从上往下扫描天然就是先遇到小层号。但如果你用了DFS后处理就需要保证“严格大于时才更新”这一原则。还有一种情况要注意如果同一层内部没有节点不会出现因为层号只有存在节点才算一层。二叉树中不存在“空层”。所以不会出现层号断档的问题levelSum数组的长度和最大层号正好一致。这个细节在DFS解法里帮我们省了很多事。4.3 用long还是intC/Java/Python的溢出细节节点个数最多1万每个节点值最大10^5那么一层的和最大是10000 * 100000 10^9刚好在32位int范围内2147483647所以用int理论上不会溢出。但这里有个前提题目说节点数1到10^4如果所有节点都在一层完全二叉树最后一层这一层可能有几千个节点每个节点10^5乘积可能接近10^9int能撑住但已经是边界附近。保险起见我会把层和sum和高层用longJava的longC的long longPython的int自动变长来存。虽然这题int够用但刷题时养成“求和就想到溢出”的习惯没坏处。尤其是后续遇到节点值更大、节点更多的题比如连续子数组最大和、前缀和int溢出是常客。这里我建议用Java写的时候声明成long sum 0; long maxSum Long.MIN_VALUE;比较时自然没问题。不过要注意Long.MIN_VALUE是-9223372036854775808作为哨兵更安全。C直接long long sum 0;就行。4.4 优化思路提前剪枝、空间压缩有些同学会琢磨能不能更高效。这题已经是O(n)了理论上不可能低于O(n)因为每个节点的值都可能影响某一层的和你不访问就没法知道。所以别想着“能不能跳过某些层”——不可能。但可以在空间上做一些微优化。比如BFS中当我们发现当前队列为空时循环自然结束。如果你能用变量记住当前最大层和所在层号就不需要额外存储每一层的和。BFS版本已经做到了所以它比DFS版本更省空间——DFS需要一个长度为层数的数组而BFS只需要O(maxWidth)的队列加几个变量。另一个常被提到的优化是在层序遍历时如果某一层求和完成后发现它比之前所有层和都小很多但这不是提前结束的条件因为你不知道下一层会不会突然变大比如节点全是正的大数。所以任何剪枝都无效。接受这个“不得不全遍历”的现实别在优化上浪费时间。还有个小技巧如果题目改成“返回最大层和对应的层号和值”你同样可以顺手把maxSum一起返回。很多树形题都爱这样考你返回值的设计。5. 同类题目串联把1161放进二叉树刷题地图5.1 与力扣热题100中的哪些题相关力扣热题100里关于二叉树的题目很多比如102. 二叉树的层序遍历、103. 二叉树的锯齿形层序遍历、104. 二叉树的最大深度、107. 二叉树的层序遍历 II、199. 二叉树的右视图。这题和它们思路完全同构都基于层序遍历或者DFS记录层信息。其中和1161最像的是102题都是按层展开只不过102题要求输出每层的节点值列表1161要求输出每层的和并比较大小。如果你能把102题写熟1161基本就是改三行的事求和代替收集列表再用一个变量记录最大层。所以刷题建议不要孤立地刷把互相之间只差一点点条件变化的题放在一起刷效率最高。再比如107题要求从叶子层向上输出其实底层遍历顺序和1161一样只是最后需要反转结果。还有199题右视图本质上也是层序遍历只取每一层的最后一个节点。掌握一种“层序模板”这些题都能快速套上。5.2 同类题目的识别特征与通用解法怎么判断一道二叉树题适合用BFS还是DFS我的经验是如果题目明确说“按层”“从上到下”“第几层”“最大层”“最小深度”等关键词优先想BFS。如果题目问的是“路径和”“节点间距离”“树的直径”这类和方向、路径相关的问题DFS更顺手。1161完美符合“按层”特征所以BFS是首选。但这里我想强调一下通用套路让递归函数多带一个depth参数然后用一个数组保存每层的信息和、最大值、最小值、节点数、平均值……这是解决所有“分层统计类”题目的万金油。无论题目换成“求每层平均值”637、“求每层最大值”515写法都几乎一样。// 637. 二叉树的层平均值DFS套路 void dfs(TreeNode root, int depth, ListDouble sum, ListInteger count) { if (root null) return; if (sum.size() depth) { sum.add(0.0); count.add(0); } sum.set(depth - 1, sum.get(depth - 1) root.val); count.set(depth - 1, count.get(depth - 1) 1); dfs(root.left, depth 1, sum, count); dfs(root.right, depth 1, sum, count); }你看就是多维护一个计数器而已。所以刷透1161的价值不只在一题本身它帮你把一类题都打通了。5.3 每日一题的正确打开方式力扣的每日一题往往不是随机出现的而是会按照某个专题周期滚动。今天遇到二叉树可能明天还是二叉树也可能跳到动态规划。所以不要只盯着当天的题目建议把最近一周的题目放到一起看总结相同点和差异性。另外做每日一题时建议先自己思考5分钟写一遍暴力/朴素解法再去看题解优化。以1161为例很多人上来就能写BFS但不一定能想到DFS数组版本。如果你能自己写出两种解法再顺带看看国际版讨论区里的O(1)空间或“单队列计数器”的妙招你的收获会翻倍。我习惯在做完每日一题后写一个简短的复盘笔记包括题意本质是什么、用了什么数据结构、能否用另一种遍历方式做、和之前哪道题相似。这个习惯坚持下来你会发现一个月后刷题速度明显提升。最后分享一点个人感受这道题我前前后后写过很多遍每次重新写都能发现新东西。有一次我把sum maxSum不小心写成了sum maxSum结果提交后答案错在了一大堆有相同层和的用例上。还有一次为了省声明我直接用了Integer.MIN_VALUE但忘了导入包编译报错才意识到。这些细节看着小真到面试时手写代码每一个都是扣分点。如果你正在刷力扣建议把1161当成一道“基础模板题”来练。先白纸写BFS再写DFS然后试着用C、Java、Python各写一遍。等你能闭着眼把层序遍历写对后面遇到右视图、锯齿遍历、最大层和都会觉得轻松很多。刷题不在于贪多把一道简单题做透比囫囵吞枣十道题更有用。这大概就是每日一题真正的意义所在。