在每个树行中找最大值 (Find Largest Value in Each Tree Row)

1. 题目描述

题目背景： 在二叉树的算法竞赛题目中，考察“层级信息”是一类非常经典的题目。本题要求在给定的二叉树结构中，提取出每一层的关键统计量——最大值。

任务描述： 给定一棵拥有 $n$ 个节点的二叉树。你需要计算并输出该树中每一层节点的最大权值。

输入格式：

1. 第一行包含一个整数 $n$ ($0 \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$ 为第 $i$ 个节点的左孩子编号。
   • $r_i$ 为第 $i$ 个节点的右孩子编号。
3. 节点编号从 $1$ 到 $n$。如果 $l_i$ 或 $r_i$ 为 $0$，则表示该孩子不存在。
4. 根节点始终为编号 $1$（若 $n > 0$）。

输出格式： 输出一行若干个整数，表示从根节点开始，每一层节点的最大值。整数之间用空格分隔。

样例 1： 输入：

6
1 2 3
3 4 5
2 0 6
5 0 0
3 0 0
9 0 0

输出：

1 3 9

(解释：第0层是{1}，最大值1；第1层是{3, 2}，最大值3；第2层是{5, 3, 9}，最大值9)

样例 2： 输入：

3
1 2 3
2 0 0
3 0 0

输出：

1 3

数据规模：

• $0 \le n \le 10^4$
• 节点的权值在 32 位有符号整数范围内。

2. 预备知识点

1. 二叉树的静态存储：在 NOI 竞赛中，通常使用结构体数组 struct Node { int v, l, r; } tree[MAXN] 来存储树，避免频繁申请内存。
2. 搜索算法 (BFS/DFS)：
   • BFS (广度优先搜索)：天然按层遍历，最适合处理层级问题。
   • DFS (深度优先搜索)：通过传递当前深度参数 depth 也可以实现。
3. 数值极值处理：由于权值可能达到 -2^31，初始化最大值时应使用 long long 的极小值或 INT_MIN。

3. 启发式思维引导

第一步：可视化结构

请在草稿纸上根据样例 1 画出树状图：

• 节点 1 连向 2 和 3。
• 节点 2 连向 4 和 5。
• 节点 3 连向 6。 此时，请用彩色笔在每一层上画一个圈。你会发现，问题变成了“统计每一个圈内的最大数”。

第二步：选择工具（BFS vs DFS）

• 若使用 BFS：我们需要一个队列。

  • 关键观察：当队列里全是某一层的节点时，队列的当前长度就是这一层的“总人数”。
  • 操作：一口气弹出这“总人数”个节点，同时把它们的子节点加入队列。

• 若使用 DFS：我们需要一个动态数组 res。

  • 关键观察：res[depth] 可以存储第 depth 层的当前最大值。
  • 操作：每访问到一个节点，比较 res[depth] 和当前节点值。

第三步：复杂度分析与思考

• 时间复杂度：每个节点必须且只能访问一次，因此是 $O(n)$。对于 $10^4$ 的数据，运行时间通常在 1ms 左右。
• 空间复杂度：
  • BFS 需要队列，最坏情况（满二叉树底层）空间 $O(n)$。
  • DFS 需要递归栈，最坏情况（链状树）空间 $O(n)$。

第四步：时间复杂度优化建议

在 NOI 考场上，若 $n$ 较大（如 $10^6$），注意：

1. 减少封装：使用静态数组代替 std::vector。
2. 输入优化：使用 scanf 或快读 read() 提高读取效率。
3. 预分配空间：如果使用 vector 存储结果，预先 reserve 空间。

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

以下流程图展示了如何在不使用复杂数据结构的情况下实现层级最大值统计：

graph TD
    A(开始) --> B{N 等于 0 吗}
    B -- 是 --> C(直接退出)
    B -- 否 --> D(将根节点 1 入队)
    
    D --> E{队列是否为空}
    E -- 是 --> F(输出所有记录的最大值)
    F --> G(结束)
    
    E -- 否 --> H(获取当前队列的大小 currentSize)
    H --> I(设置 levelMax 为最小整数)
    I --> J(循环计数 i 从 1 到 currentSize)
    
    J -- 循环中 --> K(弹出队首节点 u)
    K --> L(比较并更新 levelMax 为 u 的权值与 levelMax 的较大者)
    L --> M{u 是否有左孩子}
    M -- 有 --> N(左孩子入队)
    M -- 无 --> O{u 是否有右孩子}
    N --> O
    O -- 有 --> P(右孩子入队)
    O -- 无 --> J
    
    J -- 循环结束 --> Q(将 levelMax 存入结果序列)
    Q --> E

5. 读题关键词总结

在 NOI 题目中，看到以下词汇时要迅速联想对应模型：

1. “每一层” (Each Row/Level)：

   • 这是 BFS 的核心标志。
   • 如果题目要求层与层之间有交互（如锯齿形遍历），BFS 更方便。

2. “二叉树” + “编号”：

   • 提示使用静态数组存储：tree[idx].left, tree[idx].right。

3. “最大值” (Largest Value)：

   • 警示点：注意权值的下界。如果节点值可能是 INT_MIN，你的初始比较值必须比 INT_MIN 还要小，或者直接用该层的第一个节点值初始化。

4. $N \le 10^4$：

   • 属于中小型规模，无需担心理论上的 $O(N \log N)$ 或 $O(N)$ 复杂度差异，重点应放在代码的准确性和边界处理（如空树）上。