LeetCode 637. 二叉树的层平均值

约 5 分钟
文章信息 9 个分类 4 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 2-5 面试经典 150 题 字节 微软
标签
深度优先搜索 树 广度优先搜索 二叉树

题目描述

✅ 637. 二叉树的层平均值

image-20260928224542595

image-20260928224542596

题意分析

按从上到下的顺序，返回二叉树每一层节点值的算术平均数。每层都使用自己的总和与节点数量，不能把之前层的节点混进来，也不需要保存这一层的全部数值。

节点值是整数，但平均值可能含小数，因此答案使用浮点数。题目允许节点值达到 32 位整数边界，多个节点的总和还需要比单个节点更宽的整数类型。

解法：层序遍历

核心思路

[!blue]

队列按层组织待处理节点。每轮开始时，队列中全是当前层，先保存 size，再恰好扫描这 size 个节点。期间追加到队尾的孩子属于下一层，不参与当前统计，因而 size 既划定本轮范围，也是本层平均数的分母。

将本层 sum 初始化为零，读取节点时累加其值。处理完 size 个节点，sum 就是当前层全部节点的和，计算一次 sum / size 并加入结果，然后再为下一层重新清零。

代码用 Java long、Go int64 求和。题目最多有 $10^4$ 个节点，单个节点值在 32 位整数范围内，64 位总和足以容纳；除法前再转成浮点数，保留非整数的平均值。若先做整数除法，再把商转成浮点，丢失的小数已经无法恢复。

Java 边处理边出队；Go 在本层读取 queue[0..size)，最后统一执行 queue = queue[size:]。二者都会在下一轮只保留下一层待处理节点。循环只在队列非空时进入，所以作为分母的 size 始终大于零。

解题步骤

  1. 将根节点入队；代码也处理空根，直接返回空结果。
  2. 保存本层节点数 size，创建初始为零的 64 位 sum。
  3. 只遍历本层节点，累加节点值，并将非空孩子放入队尾。
  4. 整层完成后，将 sum 转为浮点数再除以 size，追加一个结果，继续下一层。

代码实现

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)
        var sum int64

        for i := 0; i < size; i++ {
            node := queue[i]
            sum += int64(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)$，每个节点只入队、处理一次，每层的求平均为常数时间。
  • 空间复杂度：不计输出为 $O(w)$，其中 $w$ 是最大层宽。队列最多同时容纳相邻两层的部分节点，规模与最大层宽同阶；答案每层一个数，占 $O(h)$，其中 $h$ 是树高。

关键点总结

[!green]

  • 分母是开始时固定的本层数量，不是处理途中变化的队列长度。
  • 先做整数除法再转浮点，已经丢失的小数无法恢复。
  • Go 按层截掉已处理前缀，与保留全部历史的追加队列不同。

易错点总结

[!yellow]

  • 总和不逐层清零，会混入以前层的值。
  • 用窄整数累加大量大节点值，可能在除法前溢出。
  • 把平均值追加放进节点循环，会让一层输出多个数。

相似题目

题目 难度 关联与区别
102. 二叉树的层序遍历 中等 BFS分层相同，本题对每层的和与节点数求平均，不必保存该层全部数值。
1161. 最大层内元素和 中等 同样按层求和，原题比较层和大小，本题还除以该层节点数。
103. 二叉树的锯齿形层序遍历 中等 按层遍历并在同一层内聚合；本题累计每层总和及节点数，该题交替调整每层输出方向。
107. 二叉树的层序遍历 II 中等 按层遍历并在同一层内聚合；本题累计每层总和及节点数，该题把自顶向下的层结果反转。
199. 二叉树的右视图 中等 按层遍历并在同一层内聚合；本题累计每层总和及节点数，该题每层只取最右节点。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/67992061
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！