LeetCode 1161. 最大层内元素和
题目描述
题意分析
对二叉树每一层的全部节点值求和，找到层和最大的那一层，并返回它的层号。根是第一层；如果多个层的和同为最大值，返回其中最小的层号。
比较的是整层总和，不是层内最大节点值或最多节点数。节点值可以为负，所以最大层和也可能为负；题目保证树非空，并且节点数与值范围允许层和使用 32 位整数。
解法：BFS 分层求和并保留最早最大值
核心思路
[!blue]
答案按层聚合，可以用 BFS。每轮开始时，队列中尚未处理的节点恰好属于同一层，先记住这一层的节点数，只弹出这么多个节点，便能独立计算当前层的和。
处理节点时，它的非空孩子追加到队尾，属于下一层。固定本轮数量后，这些新入队节点不会提前混入当前层；本轮结束时，待处理部分也就自然变成下一层，层号可以增加一次。
历史最大和初始化为比任意合法层和都小的整数，而不是零，才能让全负树中的真实层参与比较。只有当前层和严格大于历史最大值才更新答案；BFS 按层号递增处理，相等时保留旧答案，就自动保留了并列中的最小层号。
Java 队列会弹出已经处理的节点；Go 代码用
head在一个不断追加的切片中前移，所以本层大小是len(queue) - head，不能使用整个切片长度。两种写法的待处理边界含义一致，但 Go 仍保留已处理元素，空间分析要分别说明。
解题步骤
- 将根节点放入队列，层号从零起步，最大和置为最小整数，答案层号初始为一。
- 每轮固定尚未处理节点数，层号加一，并把本层和重置为零。
- 处理恰好这一层的节点，累加节点值，把非空孩子加入队尾。
- 当前层和严格更大时，更新最大和与层号；相等时保持旧答案。
- 全部节点处理完后返回答案层号。
代码实现
class Solution {
public int maxLevelSum(TreeNode root) {
Queue<TreeNode> queue = new ArrayDeque<>();
// 根节点单独构成第 1 层
queue.offer(root);
// 和最大的层号，兜底取合法下界 1
int ans = 1;
// 初值要比任何层和都小，不能写 0
int maxSum = Integer.MIN_VALUE;
// 当前正在处理的层号
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 {
// 根节点单独构成第 1 层
queue := []*TreeNode{
root,
}
// 和最大的层号，兜底取合法下界 1
ans := 1
// 初值要比任何层和都小，不能写 0
maxSum := -1 << 31
// 当前正在处理的层号
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)$，每个节点入队、处理一次，每层只做一次总和比较。
- 空间复杂度：Java 队列为 $O(w)$，
w为最大层宽，处理途中至多同时保存相邻两层的部分节点；Go 切片保留全部加入过的节点，因此当前实现为 $O(n)$。
关键点总结
[!green]
- 先固定层大小，再把孩子入队，保证求和范围只属于当前层。
- 最大和必须允许负值，不能用零作为未找到答案的下界。
- 按层递增搜索并只在严格更大时更新，自然满足最小层号的并列规则。
- 返回层号，层和只用于比较，不能混淆两者。
易错点总结
[!yellow]
- 本层和没有归零，会把不同层的累计值拿来比较。
- 内层循环动态读取不断增长的队列长度，会把下一层提前并入本层。
- 使用大于等于更新，会在并列时改成更深的层号。
- 最大和初始化为零，全负树的任何层都无法正确刷新。
- Go 用整个切片长度作为本层大小，忽略前面已经处理的元素，会重复处理或越界。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 同样按层锁定队列长度，原题收集节点值，本题对每层求和并记录层号。 |
| 515. 在每个树行中找最大值 | 中等 | 同样做逐层聚合，原题取每层最大元素，本题比较整层总和。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！