二叉树的层平均值 (Average of Levels in Binary Tree)

1. 题目描述

题目背景： 在信息学竞赛中，对二叉树进行统计分析是常见的考察点。除了寻找最值，有时我们需要了解每一层节点的整体分布情况，例如计算每一层权值的平均值。

任务描述： 给定一个拥有 $n$ 个节点的二叉树。请你计算每一层节点的平均值，并按从根行到叶行的顺序输出。

输入格式：

1. 第一行包含一个整数 $n$ ($1 \le n \le 10^4$)，表示节点总数。
2. 接下来的 $n$ 行，每行包含三个整数 $v_i, l_i, r_i$：
   • $v_i$ 为第 $i$ 个节点的权值 ($-2^{31} \le v_i \le 2^{31}-1$)。
   • $l_i$ 为左孩子编号。
   • $r_i$ 为右孩子编号。
3. 节点编号从 $1$ 到 $n$。如果孩子不存在，则编号为 $0$。根节点固定为编号 $1$。

输出格式： 输出一行若干个实数，表示每一层的平均值。 注意：为保证精度，请输出到小数点后第 5 位。

样例 1： 输入：

5
3 2 3
9 0 0
20 4 5
15 0 0
7 0 0

输出：

3.00000 14.50000 11.00000

(解释：第0层是{3}，均值3；第1层是{9, 20}，均值14.5；第2层是{15, 7}，均值11)

样例 2： 输入：

5
3 2 3
9 4 5
20 0 0
15 0 0
7 0 0

输出：

3.00000 14.50000 11.00000

(解释：第1层是{9, 20}，第2层是{15, 7}，逻辑同上)

2. 预备知识点

1. 二叉树存储：静态数组 struct 存储法。
2. 层序遍历 (BFS)：最契合“层”级统计的算法。
3. 精度与溢出处理：
   • 溢出隐患：单层节点权值之和可能超过 int 范围（$2^{31}-1 \times 10^4$），求和变量必须使用 long long。
   • 浮点运算：平均值计算公式为 (double)sum / count。
4. C++14 标准输出：使用 fixed 和 setprecision(5)。

3. 启发式思维引导

第一步：对比思考

在草稿纸上画两棵树。

• 问题 A：求每一层的最大值（上一题）。
• 问题 B：求每一层的平均值（本题）。
• 思考：两者的共性是什么？
  • 答：都需要“分层”。你需要一个容器，在处理完一层的所有节点后，才输出该层的统计结果。

第二步：累加器设计

对于每一层，我们需要维护两个变量：

1. long long sum：存储该层所有节点的权值总和。
2. int count：存储该层有多少个节点。

• 避坑指南：为什么 sum 不用 double？在 NOI 中，先用整数类型求精确和，最后一步再转浮点数，可以最大限度减少累积误差。

第三步：复杂度与优化

• 时间复杂度：每个节点入队出队一次，$O(N)$。
• 空间复杂度：
  • BFS 队列最宽处约为 $N/2$。
  • 如果用 DFS 配合两个数组（sums[depth] 和 counts[depth]），空间复杂度则与树高成正比。

4. 算法流程图 (基于 BFS 策略)

graph TD
    Start(开始) --> Init[初始化队列 Q 并将根节点 1 入队]
    Init --> WhileQ{Q 是否不为空}
    
    WhileQ -- 否 --> End(结束)
    WhileQ -- 是 --> GetSize(获取当前层节点数 sz)
    
    GetSize --> LevelInit(初始化 sum 为 0 且 count 等于 sz)
    LevelInit --> ForLoop{循环 i 从 1 到 sz}
    
    ForLoop -- 结束 --> CalcAvg(计算 avg 等于 sum 除以 count)
    CalcAvg --> PrintAvg(输出保留五位小数的 avg)
    PrintAvg --> WhileQ
    
    ForLoop -- 迭代中 --> Deq(弹出队首节点 u)
    Deq --> AddSum(将 u 的权值加到 sum)
    AddSum --> Left{u 是否有左孩子}
    Left -- 有 --> EnqL(左孩子入队)
    Left -- 无 --> Right{u 是否有右孩子}
    EnqL --> Right
    Right -- 有 --> EnqR(右孩子入队)
    Right -- 无 --> ForLoop

5. 读题关键词总结

在 NOI 赛场上，看到以下关键词应形成条件反射：

1. “平均值” (Average)：

   • 核心公式：总和 / 数量。
   • 警示：注意数据范围，计算总和时务必检查是否会 int 溢出。

2. “每一层” (Each Level)：

   • 核心算法：BFS 是首选。
   • 技巧：在 while(!q.empty()) 内部第一行写 int sz = q.size(); 是固定套路。

3. “精度要求” (Precision)：

   • 实现：printf("%.5f", ans) 或 cout << fixed << setprecision(5) << ans。
   • 注意：在计算过程中尽量保持高精度（使用 double 而非 float）。

4. $N \le 10^4$：

   • 意义：数据量适中，$O(N)$ 算法可以稳稳通过。即便使用 std::vector 或 std::queue 也不用担心常数过大。

教练寄语： 层序遍历是树论的基石。在处理“平均值”时，最核心的技巧是先求和再除法。如果边加边除（即：avg = avg + val/sz），会产生严重的浮点误差，这在 NOI 评分中是致命的。切记！