你好，同学。欢迎回到 NOI 竞赛辅导专题。上一节课我们学习了正向的层序遍历，今天我们要讨论它的一个变体——二叉树的层序遍历 II。

在 LeetCode 上这是第 107 题。虽然看似只是输出顺序的改变，但在 NOI 竞赛中，这种“逆序处理”的思想在动态规划和拓扑排序中非常常见。

二叉树的层序遍历 II (Binary Tree Level Order Traversal II)

时间限制：1.0s 内存限制：256MB

【问题描述】 给定一棵包含 $N$ 个节点的二叉树，每个节点由其节点值、左子节点索引和右子节点索引定义。 请你设计算法，输出该二叉树 自底向上 的层序遍历结果。 即：先输出叶子节点所在的最底层，最后输出根节点所在的第 0 层。每一层内部的节点按照 从左到右 的顺序排列。

【输入格式】 第一行包含一个整数 $N$ ($0 \le N \le 2000$)，表示节点的总数。 接下来的 $N$ 行，每行包含三个整数 $V_i, L_i, R_i$：

• $V_i$：第 $i$ 个节点的值 ($-1000 \le V_i \le 1000$)。
• $L_i$：第 $i$ 个节点的左子节点编号。
• $R_i$：第 $i$ 个节点的右子节点编号。 节点编号范围为 $0$ 到 $N-1$。若 $L_i$ 或 $R_i$ 为 $-1$，则表示该子节点为空。 注意：入度为 0 的节点视为根节点。若 $N=0$ 则无输入。

【输出格式】 输出若干行，每行代表树的一层。 每行中的值用单个空格隔开，行末不得有多余空格。

【样例输入】

5
3 1 2
9 -1 -1
20 3 4
15 -1 -1
7 -1 -1

【样例输出】

15 7
9 20
3

【数据说明】 对于 100% 的数据，$0 \le N \le 2000$。树的深度不超过 $N$。

二、 预备知识点

本题在正向层序遍历的基础上，增加了对结果序列处理的要求：

1. 广度优先搜索 (BFS)：利用队列保持层次性。
2. 序列反转 (Reverse Operation)：利用 std::reverse 或 std::stack 处理输出顺序。
3. 容器操作：熟练使用 std::vector<std::vector<int>> 进行嵌套存储。

三、 思路提示

思考 1：顺序还是逆序入队？ 如果我们想得到“自底向上”的结果，能否直接从叶子开始搜？ 提示：由于二叉树只有指向子节点的指针（通常），从下往上搜很难定位。所以我们依然维持“从根向叶”的 BFS 顺序。

思考 2：如何实现“自底向上”？ 正向 BFS 得到的结果是 [[Level 0], [Level 1], ..., [Level N]]。 提示：在 C++ STL 中，有一个非常高效的算法 std::reverse(first, last)。我们可以先按标准层序遍历存储结果，最后将整个二维容器进行行间的翻转。

四、 启发式草稿纸推演

请拿出你的草稿纸，我们来模拟如何通过“正向搜索 + 结果反序”达成目标。

1. 逻辑分层图

假设树结构如下：

      3
     / \
    9  20
      /  \
     15   7

• Step A (BFS 队列运行)：
  • Queue: {3} -> 处理后结果集: {{3}}
  • Queue: {9, 20} -> 处理后结果集: {{3}, {9, 20}}
  • Queue: {15, 7} -> 处理后结果集: {{3}, {9, 20}, {15, 7}}
• Step B (翻转操作)：
  • 将结果集 Res 整体翻转。
  • 原本 Res(0) 是 (3)，翻转后变成 Res(2)。
  • 得到：{{15, 7}, {9, 20}, {3}}。

2. 时间与空间复杂度分析

• 时间复杂度：
  • BFS 遍历所有节点：$O(N)$。
  • 反转二维数组：反转操作只涉及外层 vector 的指针/引用交换，复杂度为 $O(H)$，其中 $H$ 为树的高度。总时间复杂度仍为 $O(N)$。
• 空间复杂度：
  • 需要一个队列存储节点及一个二维数组存储结果，均为 $O(N)$。

3. 算法逻辑流程图 (Mermaid 语法)

graph TD
    Start(开始) --> CheckRoot{根节点是否存在}
    CheckRoot -- 否 --> End(返回空结果)
    CheckRoot -- 是 --> Init(初始化队列并将根节点入队)
    Init --> LoopQueue{队列是否为空}
    LoopQueue -- 否 --> GetSize(获取当前层节点数 count)
    GetSize --> LevelProc(遍历 count 次并保存到临时数组)
    LevelProc --> Children(将子节点顺序入队)
    Children --> SaveLevel(将临时数组存入结果列表 Res)
    SaveLevel --> LoopQueue
    LoopQueue -- 是 --> ReverseOp(调用 std-reverse 翻转 Res)
    ReverseOp --> Output(按格式输出 Res)
    Output --> End

五、 读题理解关键词

在 NOI 题目中，遇到以下描述需警惕：

1. “自底向上” (Bottom-up)：这是本题的灵魂关键词。它暗示你结果的顺序是层级的逆序。
2. “逐层从左到右”：这意味着在每一层内部，顺序依然是标准的。这排除了一些需要镜像处理的情况。
3. “返回节点值列表”：在竞赛输出时，要注意每一层节点之间通常有空格，而行末不应有空格（NOI 严格格式检查）。

金牌教练建议： 虽然可以使用 std::vector::insert(v.begin(), ...) 每次插入到头部，但在 std::vector 中，头部插入会导致 $O(N)$ 的内存移动。在 NOI 这种对时间限制敏感的比赛中，始终推荐先 push_back 完再统一 reverse，或者预计算深度后按索引填入。

好了，按照这个思路，尝试去实现你的 Solution 吧！注意处理好空树的情况。