LeetCode 637. 二叉树的层平均值
目录
题目描述
题意分析
给一棵二叉树，要求返回一个
double数组，第i个元素是第i层（根为第 0 层）所有节点值的算术平均值。答案长度等于树的高度。求平均值意味着每一层需要两个量：这一层节点值的总和与这一层的节点个数。个数不是可以事后推算的，必须在遍历时就知道边界在哪里，所以核心难点仍然是「如何把遍历切分成整齐的层」。
有两个约束会直接影响实现细节。第一，节点值范围是 $[-2^{31}, 2^{31}-1]$，而节点总数最多 $10^4$，所以一层的和可能远超
int范围——比如 5000 个 $2^{31}-1$ 相加。累加变量必须用 64 位类型，这是本题唯一的隐藏坑，也是它虽被标为简单却值得一写的原因。第二，返回类型是浮点数，除法必须走浮点通道，整数相除会被截断。题目还说明「与标准答案相差 $10^{-5}$ 以内视为正确」，这是在告诉你不必纠结精度控制，用
double直接算即可，不需要任何舍入处理。边界方面题目保证树至少有一个节点，但实现上仍应处理
root == null返回空数组，以免入队空指针。另外树可能退化成一条链，每层只有一个节点，平均值就是节点值本身。
解法：层序遍历
核心思路
直接用队列做宽度优先遍历，弹出节点就把孩子推进去，这样访问顺序是对的，但队列里同时混着相邻两层的节点，弹出时无从判断当前节点属于哪一层，也就凑不齐「本层和」与「本层个数」这两个量。这是瓶颈。
关键观察是：在开始处理某一层之前的那个瞬间，队列里的元素恰好就是这一层的全部节点。因为上一层已经全部弹完，下一层还没被推入。于是只要在这个时刻把
queue.size()冻结进局部变量size，再严格只处理size个节点，层的边界就被精确地切开了——而且这个size正好就是求平均值需要的分母，一举两得。维持的不变量是：每次进入外层循环时，队列中的元素恰好构成树的某一整层，且顺序为从左到右。初始时队列只有根节点，构成第 0 层，成立；内层循环弹出恰好
size个节点并推入它们所有非空孩子，退出时队列里正好是下一层的全部节点，不变量得以维持。某一层不再产生孩子时队列变空，外层循环终止。有了这个不变量，聚合就是顺带的事：内层开始前把
sum置 0，循环中累加每个弹出节点的值，内层结束后sum / size就是这一层的平均值。最后一个必须想清楚的点是类型。
sum声明为long（Go 里int在 64 位平台上本就是 64 位）才能装下极端情况下的层和；而sum / size如果两边都是整数会做整数除法，[1, 2]这一层会算出 1 而不是 1.5，所以要写成sum * 1.0 / size或显式转成浮点后再除。
解题步骤
- 空树直接返回空列表：
root == null时不存在任何层。这一步也保证了不会把null推进队列，避免内层取node.val时空指针。- 建队列并推入根节点：让第一轮外层循环时队列恰好是第 0 层，不变量从一开始就成立。Java 用
ArrayDeque而非LinkedList，常数更小；Go 用切片配合每层结束时的queue = queue[size:]整段截断，比逐个截断更省。- 外层循环条件
!queue.isEmpty()：队列空说明上一层没有孩子，遍历结束。- 进入外层循环立刻冻结
size = queue.size()：这一行是全题核心。必须在弹出任何节点之前取值并存进局部变量；写成i < queue.size()会因为孩子入队而不断变大，层的边界立即失效，分母也跟着错。sum声明为long并每层清零：long是为了容纳可能超出int的层和；每层清零是因为它的语义是「本层的和」，跨层累积会让第二层往后全部偏大。- 内层循环恰好执行
size次：弹出节点、累加node.val、把非空的左右孩子按顺序推入。判空后再入队，保证队列里永远没有null。- 内层结束后计算并追加
sum * 1.0 / size：乘1.0是为了把整数除法提升成浮点除法。追加动作必须在内层循环之外、外层循环之内，位置放错会导致每个节点各产生一个结果。- 返回结果列表：外层退出时所有层都已处理完。
以样例树走一遍：根为 3，左孩子 9、右孩子 20，节点 20 的左孩子 15、右孩子 7。答案应为
[3.0, 14.5, 11.0]。初始：队列
[3]，结果[]。第一轮外层：
size = 1，sum = 0。弹出 3，sum = 3；推入 9 和 20。内层结束，追加3 / 1 = 3.0。队列变成[9, 20]，恰好是完整的第 1 层。第二轮外层：
size = 2，sum = 0。弹出 9，sum = 9，它没有孩子；弹出 20，sum = 29，推入 15 和 7。内层只跑了 2 次就停——尽管此时队列里已有 2 个新元素，冻结的size保证它们不会被算进本层。追加29 / 2 = 14.5。队列变成[15, 7]。第三轮外层：
size = 2，sum = 0。弹出 15（sum = 15）、弹出 7（sum = 22），两者都无孩子。追加22 / 2 = 11.0。队列变空。外层条件不成立，返回
[3.0, 14.5, 11.0]，正确。特别注意第二层：如果把
sum * 1.0 / size写成sum / size且sum是整型，这一层会算出 14 而不是 14.5，直接判错。而如果sum用int，把这层换成两个 $2^{31}-1$ 的节点，累加会溢出成负数，平均值变成一个负的巨大数值。
代码实现
class Solution {
// 每层结束后计算平均值并加入结果。
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
long 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);
}
}
res.add(sum * 1.0 / size);
}
return res;
}
}
func averageOfLevels(root *TreeNode) []float64 {
// 每层结束后计算平均值并加入结果。
res := make([]float64, 0)
if root == nil {
return res
}
queue := make([]*TreeNode, 0)
queue = append(queue, root)
for len(queue) > 0 {
size := len(queue)
sum := 0
for i := 0; i < size; i++ {
node := queue[i]
sum += node.Val
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
res = append(res, float64(sum)/float64(size))
queue = queue[size:]
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$，其中 $n$ 是节点总数。每个节点恰好入队一次、出队一次，出队时做一次累加和两次空判断，全是常数操作；每层额外做一次除法，层数不超过 $n$。
- 空间复杂度：$O(w)$，其中 $w$ 是树的最大宽度，即队列长度的峰值。完全二叉树的最后一层约有 $n/2$ 个节点，所以最坏是 $O(n)$；退化成链时每层只有一个节点，只需 $O(1)$。返回数组长度等于树高，属于必要输出不计入。
关键点总结
- 进入每轮循环时先冻结
queue.size()，是把混层的队列切成整齐层次的唯一关键；本题还额外享受一个好处——这个size直接就是平均值的分母，不必再单独计数。这套骨架在右视图、锯齿遍历、层最大值等题里完全通用。- 聚合前先问一句中间量会不会溢出：节点值可达 $2^{31}-1$ 而层宽可达数千，
int装不下层和。凡是「大量元素求和再做统计」的题，累加变量默认用 64 位是最省心的习惯。- 结果是浮点数时，除法两侧至少要有一侧是浮点类型；
sum * 1.0 / size或(double) sum / size都行，写成(double) (sum / size)则是先截断后转换，等于没救。- 不变量「每次外层循环开始时队列恰为完整一层」比代码更值得说给面试官听，它一句话解释了内层为什么跑
size次、新入队的孩子为什么不会被误算。- 本题也可以用深度优先做：递归时带层号，分别维护每层的和与计数两个数组，最后逐层相除。时间同为 $O(n)$，空间是 $O(h)$，树很宽时反而更省——能主动比较两种遍历的空间取舍是加分项。
易错点总结
sum用int累加：一层里有两个 $2^{31}-1$ 的节点时，累加溢出为负数，平均值变成一个负的大数，而正确答案是 $2^{31}-1$。- 写成
sum / size做整数除法：[1, 2]这一层会得到 1.0 而不是 1.5，所有非整除的层都会偏小。- 写成
(double) (sum / size)：截断已经发生，再转类型无济于事，同样把 14.5 变成 14.0。- 内层循环条件直接写
i < queue.size()：孩子入队让上界不断变大，样例树第一轮就会把第 1 层也卷进来，sum变成 32、size变成 3，返回 10.67 之类的错乱值。size在弹出若干节点之后才取：层边界整体后移，样例树会把节点 9 划到下一层，结果长度和数值全错。sum忘记每层清零：第二层的和里混入了第一层，样例树会得到[3.0, 16.0, ...]，之后每层都偏大。res.add(...)写在内层循环里：每个节点各产生一个结果，样例树会返回 5 个元素而不是 3 个。- 忘记
root == null的判断：null被推进队列，内层访问node.val立刻空指针。- 入队前不判断孩子是否为空：
null进队后不仅下一层取值会崩，size里还混进了不存在的节点，分母偏大导致平均值偏小。- Go 里用
queue = queue[1:]逐个截断：功能正确但底层数组无法释放，深树上内存持续增长；按层整段queue = queue[size:]更稳妥。- 误以为可以先求整棵树的和再按层拆：不同层的节点在一维遍历里无法区分归属，
[3,9,20]与[3,9,20,null,null,15,7]的总和相同但答案完全不同。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 515. 在每个树行中找最大值 | 中等 | 聚合换成取最大值，初值必须用真实下界而非 0，无溢出风险 |
| LCR 044. 在每个树行中找最大值 | 中等 | 与 515 同题 |
| 102. 二叉树的层序遍历 | 中等 | 每层输出全部节点值而非聚合成一个数，是本题骨架的最裸形态 |
| 剑指 Offer 32 - II. 从上到下打印二叉树 II | 简单 | 与 102 同题 |
| 199. 二叉树的右视图 | 中等 | 只取每层最后一个节点，用 i == size - 1 判断即可 |
| LCR 046. 二叉树的右视图 | 中等 | 与 199 同题 |
| 513. 找树左下角的值 | 中等 | 只要最后一层的第一个值，可先入右孩子后取最后弹出的节点 |
| LCR 045. 找树左下角的值 | 中等 | 与 513 同题 |
| 1302. 层数最深叶子节点的和 | 中等 | 只需最后一层的和，让每层的和覆盖前一层即可，无需保存全部层 |
| 103. 二叉树的锯齿形层序遍历 | 中等 | 奇数层需反向收集，用双端队列头插比整体反转更省一次遍历 |
| 107. 二叉树的层序遍历 II | 中等 | 层次结果自底向上，收集时头插或最后整体反转 |
| 662. 二叉树最大宽度 | 中等 | 空位也计入宽度，需给节点编号并注意深链时编号溢出 |
| 958. 二叉树的完全性检验 | 中等 | 反其道而行，空节点也入队，遇空后再出现非空即判否 |
| 429. N 叉树的层序遍历 | 中等 | 孩子数量不定，内层要遍历 children 列表而非固定左右两支 |
| 剑指 Offer 32 - I. 从上到下打印二叉树 | 中等 | 输出拉平成一维数组，反而不需要冻结 size 分层 |
| 剑指 Offer 32 - III. 从上到下打印二叉树 III | 中等 | 与 103 同题 |
| 面试题 04.03. 特定深度节点链表 | 中等 | 每层结果要组装成链表，需在层内维护尾指针边遍历边接 |