LeetCode 1161. 最大层内元素和

2026-07-14 HGNULB 约 12 分钟

文章信息 3 个分类 4 个标签

分类

题目描述

✅ 1161. 最大层内元素和

题意分析

给定二叉树的根节点 root，把每一层的节点值加起来得到该层的「层内元素和」，返回层内元素和最大的那一层的层号。

题面有两个必须抠死的定义。第一是层号从 1 开始：根节点所在的是第 1 层，根的子节点是第 2 层，依此类推。所以返回值的下界是 1，任何以 0 起算的实现都会让答案整体少 1。第二是并列时返回最小的层号：如果有多层的元素和同时达到最大，答案取其中层号最小的那一层。这一点直接决定了实现细节——如果按层号从小到大依次扫描，那么更新最优解时必须用严格大于，一旦写成大于等于，后来出现的同值层就会把先出现的层顶掉，返回一个偏大的层号。

第三个容易被忽略的信号来自数据范围：节点值可以是负数（题面给出的范围是 -10^5 <= Node.val <= 10^5），因此某一层的元素和完全可能是负数，整棵树所有层的和也可能全是负数。这意味着记录「当前最大层和」的变量初值不能取 0，否则在全负数的树上一次都不会触发更新，答案变量会停留在初值上，输出一个非法层号。初值应当取一个比任何可能的层和都小的值。节点数最多 10^4、每个值绝对值最多 10^5，所以任意一层的和落在 $[-10^9, 10^9]$ 内，32 位整数足够存放，不必担心溢出。

边界情形只有一种值得单独想：题目保证树至少有 1 个节点，所以不存在空树输入；单节点树只有第 1 层，答案必然是 1。除此之外，链状树（每层只有 1 个节点）和完全二叉树（最后一层最宽）分别是「层数最多」和「单层最宽」的两个极端，实现要能同时兜住这两侧。

解法：BFS 按层求和

核心思路

求的是「层」的聚合值，而遍历的单位是「节点」，所以核心问题是如何在遍历时准确地把节点切分到各层。广度优先搜索天然满足这一点：它按距离根节点的边数递增的顺序访问节点，同一层的节点必然在队列中连续出现，不会与相邻层交错。

关键技巧是在每轮循环开始时先把队列长度快照下来。为什么这个长度恰好等于当前层的节点数？因为整个过程满足这样一条循环不变量：每次进入 while 循环体、尚未弹出任何节点时，队列中的元素恰好是第 level + 1 层的全部节点，且不含其他任何层的节点。

这条不变量可以用归纳法确认。初始时队列里只有根节点，而根节点就是第 1 层的全部节点，不变量成立。假设某轮进入循环时队列里恰好是第 $k$ 层的 $m$ 个节点，那么先把 size = m 记下来，接着做恰好 $m$ 次出队：这 $m$ 次弹出的正是第 $k$ 层的全部节点，把它们的值累加就得到第 $k$ 层的层内元素和。而这 $m$ 次弹出过程中新入队的元素，都是第 $k$ 层节点的非空子节点，也就是第 $k+1$ 层的全部节点——因为第 $k+1$ 层的每个节点必有一个父节点在第 $k$ 层，不会有遗漏；又因为只挂了第 $k$ 层节点的孩子，不会有多余。内层循环结束时，队列里剩下的正好是第 $k+1$ 层的全部节点，不变量在下一轮继续成立。

一旦每层的和都能被独立算出，剩下的就是「在一串数里找最大值的下标」。由于 BFS 保证层号是按 1、2、3……递增的顺序产出的，只要用严格大于来更新，先出现的层就永远不会被同值的后来者替换，「并列取最小层号」这个要求就自动被满足了，不需要额外记录候选集合，也不需要事后再比较一遍。

正确性也就此闭合：算法枚举了每一层且只枚举一次，每层的和都算对，最大值的更新规则又保证了并列时取到最小层号，因此返回的层号必然是符合题意的答案。

解题步骤

把根节点入队，作为第 1 层的唯一成员。题目保证树非空，所以不必额外判空；这一步同时为循环不变量提供了归纳基础。

初始化三个变量：ans = 1 记录答案层号（取合法下界作为兜底，保证任何情况下都不会返回非法值），maxSum 取一个比任何层和都小的值（如 Integer.MIN_VALUE），level = 0 记录当前处理到第几层。

只要队列非空就进入一轮循环，每一轮处理一整层。进入循环体后第一件事是取 size = queue.size()，把「本层有多少个节点」固定住。为什么必须先快照：后面的出队过程会往同一个队列里追加下一层的节点，如果把 size 写在循环条件里实时求值，边界会一直往后移，一轮就会把整棵树吞进去，层的划分彻底失效。

把 level 自增 1，表示开始处理新的一层。自增放在快照之后、累加之前，level 的值就始终与本轮正在处理的那一层对应。

用一个循环恰好弹出 size 个节点，把它们的值累加到本层的 sum；每弹出一个节点，就把它的非空左右子节点追加到队尾。判空是必需的：空节点入队后下一轮取值会直接崩溃，而且会污染下一层的节点计数。

本层遍历完后，用 sum > maxSum 判断是否更新答案。为什么是严格大于而不是大于等于：层号是递增产出的，严格大于意味着只有「严格更优」才换人，同值时保留先到的较小层号，正好对应题意。

队列耗尽说明所有层都处理完了，返回 ans。

以 root = [2,-5,8,3,null,null,-1] 走一遍（这棵树的形状是：根 2，左孩子 -5、右孩子 8；-5 只有左孩子 3，8 只有右孩子 -1）。初始 queue = [2]，ans = 1，maxSum = Integer.MIN_VALUE，level = 0。

第 1 轮：size = 1，level 变为 1。队列内容是 [2]，弹出 2，sum = 2；把 -5 和 8 入队。判断 2 > Integer.MIN_VALUE 成立，于是 maxSum = 2，ans = 1。

第 2 轮：size = 2，level 变为 2。队列内容是 [-5, 8]，依次弹出，sum = -5 + 8 = 3；-5 的左孩子 3 入队，8 的右孩子 -1 入队。判断 3 > 2 成立，于是 maxSum = 3，ans = 2。

第 3 轮：size = 2，level 变为 3。队列内容是 [3, -1]，依次弹出，sum = 3 + (-1) = 2；两个节点都是叶子，没有新节点入队。判断 2 > 3 不成立，不更新。

队列为空，返回 ans = 2。三层的和分别是 2、3、2，最大的是第 2 层，答案正确。

再用 root = [1,2,2,1,1,1,1] 看为什么必须是严格大于（一棵三层满二叉树，根为 1，第 2 层两个 2，第 3 层四个 1）。第 1 层和为 1，此时 maxSum = 1、ans = 1；第 2 层和为 2 + 2 = 4，4 > 1 成立，maxSum = 4、ans = 2；第 3 层和为 1 + 1 + 1 + 1 = 4，判断 4 > 4 不成立，ans 保持 2。最终返回 2，正是并列中最小的层号。若把条件换成 4 >= 4，第 3 层会把第 2 层顶掉，返回 3，答案就错了。

代码实现

class Solution {
    public int maxLevelSum(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root); // 根节点单独构成第 1 层

        int ans = 1; // 和最大的层号，兜底取合法下界 1
        int maxSum = Integer.MIN_VALUE; // 初值要比任何层和都小，不能写 0
        int level = 0; // 当前正在处理的层号

        while (!queue.isEmpty()) {
            int size = queue.size(); // 先快照：此刻队列里恰好是本层全部节点
            level++;
            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;
                ans = level;
            }
        }

        return ans;
    }
}

func maxLevelSum(root *TreeNode) int {
    queue := []*TreeNode{root} // 根节点单独构成第 1 层

    ans := 1           // 和最大的层号，兜底取合法下界 1
    maxSum := -1 << 31 // 初值要比任何层和都小，不能写 0
    level := 0         // 当前正在处理的层号

    for head := 0; head < len(queue); {
        size := len(queue) - head // 先快照：未处理的部分恰好是本层全部节点
        level++
        sum := 0 // 本层元素和

        for i := 0; i < size; i++ {
            node := queue[head]
            head++
            sum += node.Val

            if node.Left != nil {
                queue = append(queue, node.Left) // 下一层节点追加到队尾
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        if sum > maxSum { // 严格大于：并列时保留先出现的较小层号
            maxSum = sum
            ans = level
        }
    }

    return ans
}

复杂度分析

时间复杂度：$O(n)$，其中 n 是树的节点数。每个节点恰好入队一次、出队一次，出队时做常数次工作（一次加法、两次判空、至多两次入队）；层级循环的总轮数等于树的高度，但所有轮次的内层迭代次数加起来正好是 n，所以总代价与节点数成正比。

空间复杂度：$O(n)$，额外空间只有那一个队列，几个标量变量是 $O(1)$。队列的峰值出现在处理某一层的中途——此时队列里同时存着该层剩余的节点和已经挂上去的下一层节点，因此峰值不超过相邻两层节点数之和，量级由最宽的那一层决定。链状树最宽一层只有 1 个节点，峰值是 $O(1)$；完全二叉树的最后一层约有 $n/2$ 个节点，峰值达到 $O(n)$，这就是最坏情况。Go 版用下标 head 前移代替真出队，切片不回收已处理的元素，所以它的实际占用是 $O(n)$。

关键点总结

需要「按层」而不只是「按节点」处理时，BFS 的标准写法是在每轮循环开头先把队列长度快照成局部变量。这个长度天然等于当前层的节点数，而把它写在循环条件里实时求值会让层边界随入队不断后移。

「多个最优解取最小下标」这类要求，只要保证按下标递增的顺序扫描，再用严格大于更新最优解，就自动被满足，不需要额外维护候选集合或事后再比一轮。反过来，要取最大下标才用大于等于。

极值变量的初值应当取「不可能达到的那一侧边界」，而不是顺手写 0。0 只在确知数据非负时才安全；一旦数据可能为负，用 0 起手等价于凭空插入了一个虚假的候选值。

求「哪一个」而不是「是多少」时，答案变量和极值变量要成对更新，并且答案变量的初值要取一个合法值。这样即使更新一次都没触发，返回的也是合法输出而不是哨兵值。

编号从 0 还是从 1 开始由题面规定，不由实现习惯决定。把计数器的初值和自增位置放在一起确定，能避免整体偏移一位这种一眼看不出来的错误。

易错点总结

把比较写成 sum >= maxSum：root = [1,2,2,1,1,1,1]，第 2 层与第 3 层的和都是 4 → 后来的层把先到的顶掉，返回 3，正确答案是 2。

maxSum 初值取 0：root = [-1,-2,-3]，两层的和分别是 -1 和 -5，都不大于 0 → 循环里一次都不更新，答案变量停在初值上，若初值写成 0 就输出 0，正确答案是 1。

内层循环条件直接写 i < queue.size() 而不先快照：root = [1,7,0,7,-8]，出队时新节点不断入队把上界推远 → 一轮就把整棵树吞掉，只算出一个「层和」7，返回 1，正确答案是 2。

层号从 0 开始计数：root = [1,7,0,7,-8] → 输出 1，正确答案是 2，所有结果都比正确层号小 1；单节点树 root = [1] 会输出 0，一个题目里根本不存在的层号。

不判空就把子节点入队：root = [1,7,0,7,-8] 里 0 是叶子 → null 进了队列，下一轮取 node.val 直接抛 NullPointerException（Go 版是 nil 指针解引用 panic）；即使侥幸不崩，空节点也会让下一层的节点计数虚高。

在层内每弹出一个节点就更新一次全局最大值：这等于把「最大节点值」当成「最大层和」在比。root = [5,4,4] 第 1 层和是 5、第 2 层和是 8 → 最大节点值 5 在第 1 层，返回 1，正确答案是 2。注意官方样例 [1,7,0,7,-8] 在这种写法下也返回 2，恰好掩盖了错误，必须换用例才能测出来。

以为层和随深度单调、遇到下降就提前返回：root = [1,-100,50,60]，三层的和依次是 1、-50、60 → 在第 2 层就返回 1，正确答案是 3。层和没有任何单调性，必须扫完所有层。

用哈希表按层号累加、再遍历 keySet() 找最大：哈希表的迭代顺序不在语言规范的保证范围内 → 遍历顺序一旦不是层号递增，root = [1,2,2,1,1,1,1] 这类并列输入就可能先撞上较大的层号并把它当答案，返回 3 而不是 2。要么显式按层号排序，要么改用数组下标。

改用 DFS 却把深度当固定长度数组的下标：root = [1,2,null,3,null,4] 是一条深度 4 的左斜链 → 递归到超出预分配长度的深度时访问越界，抛出数组越界异常。DFS 写法必须用可增长的容器，或先求出树高再分配。

返回的是最大层和而不是层号：root = [1,7,0,7,-8] 最大层和是 7 → 输出 7，正确答案是 2。题目问的是「哪一层」，最后一步别拿错变量。

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	同样按层切分队列，但要输出每层的节点列表，不做层内聚合也不在层间比较
103. 二叉树的锯齿形层序遍历	中等	层内顺序变成关键，需要按层号奇偶翻转方向；本题只求和，层内顺序完全无关
107. 二叉树的层序遍历 II	中等	结果要自底向上组织，层号的方向与本题相反，得靠头插或最终反转
199. 二叉树的右视图	中等	每层只取末尾那一个节点，靠下标等于 `size - 1` 定位，不需要把整层累加
513. 找树左下角的值	中等	目标固定在最后一层的首个节点，位置由遍历顺序直接给出，没有层间取最值的比较
515. 在每个树行中找最大值	中等	层内聚合从求和换成取最大值，且每层结果都要保留，而非只输出一个层号
637. 二叉树的层平均值	简单	层内求和后还要除以该层节点数，必须同时用上层宽，并处理浮点精度
662. 二叉树最大宽度	中等	比较的是层宽而不是层和，且空位也要计入，需要给节点编号而非单纯计数
1302. 层数最深叶子节点的和	中等	同样要算层和，但目标层固定是最后一层，只需覆盖式记录，不必在层间取最大