你好，同学。很高兴看到你开始攻克树论中的基础题目。这道题在 LeetCode 上是“二叉树的层序遍历”，但在 NOI 竞赛中，它属于 “广度优先搜索 (BFS)” 在树形结构上的标准应用。

作为教练，我不会直接给你代码，但我会引导你如何在草稿纸上把这道题“算”出来。

一、 题目描述 (NOI 竞赛风格)

题目名称：二叉树的层序遍历 (Level Order Traversal) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一棵拥有 $n$ 个节点的二叉树，请输出该树按 层序遍历 得到的节点值。即：先输出第 1 层（根节点）的所有节点，再输出第 2 层的所有节点，以此类推。同一层内的节点需按从左到右的顺序排列。

【输入格式】 由于是模拟竞赛题，假设输入第一行包含一个整数 $n$，表示节点总数。接下来 $n$ 行，每行包含两个整数 $L_i, R_i$，分别表示第 $i$ 个节点的左子节点编号和右子节点编号（若无子节点则为 -1）。最后一行给出各个节点的值。 (注：在 LeetCode 原题中通过 TreeNode 指针给出，但在 NOI 线下赛中通常以数组下标形式给出。)

【输出格式】 输出若干行，每一行表示二叉树的一层，节点值之间用空格分隔。

【样例输入】

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

(表示根为 3，左儿子 9，右儿子 20；20 的左儿子 15，右儿子 7)

【样例输出】

3
9 20
15 7

【数据范围】

• 树中节点数目在 $[0, 2000]$ 范围内。
• 节点值在 $[-1000, 1000]$ 范围内。

二、 预备知识点

1. 队列 (std::queue)：先进先出 (FIFO) 的特性，是 BFS 的灵魂。
2. 动态数组 (std::vector)：用于存储每一层的结果。
3. 二叉树的存储：结构体数组或指针。
4. 分层处理逻辑：如何在标准的 BFS 中识别出一层的结束。

三、 启发式思维引导（草稿纸上的推理）

请拿出你的草稿纸，跟我一起画图：

步骤 1：形象化理解 画出一个 3 层的二叉树。

• 第一层：根节点 (Root)
• 第二层：Root 的子节点
• 第三层：Root 孙子辈的节点

步骤 2：核心矛盾——“如何断行”？ 普通的 BFS 只是把所有节点按顺序吐出来：3, 9, 20, 15, 7。 但题目要求按层输出。我们需要在程序中知道：当前的队列里，哪些是“这一层”的，哪些是“下一层”的？

步骤 3：找规律（关键点）

1. 当你准备处理第 $k$ 层时，队列里正好存放且只存放了第 $k$ 层的所有节点。
2. 此时，队列的长度 Q.size() 就是第 $k$ 层的节点个数。
3. 启发： 我们只需要在每一层处理开始前，先取一次 size，然后执行 size 次出队操作，这 size 个节点就一定是同一层的。

步骤 4：复杂度模拟

• 时间：每个节点进队一次，出队一次，复杂度 $O(N)$。
• 空间：最坏情况下（满二叉树），最后一层的节点数约为 $N/2$，队列需要 $O(N)$ 的空间。

四、 算法逻辑流程图 (Mermaid 格式)

为了避免语法错误，我将使用圆括号和简洁描述。

graph TD
    A(开始) --> B{根节点是否为空}
    B -- 是 --> C(返回空结果)
    B -- 否 --> D(将根节点入队)
    D --> E{队列是否为空}
    E -- 是 --> F(结束并输出)
    E -- 否 --> G(获取当前队列长度 current_size)
    G --> H(创建本层临时列表 current_level)
    H --> I{循环 current_size 次}
    I -- 循环中 --> J(出队一个节点 node)
    J --> K(将 node 的值存入 current_level)
    K --> L{node 左子是否存在}
    L -- 是 --> M(左子入队)
    L -- 否 --> N{node 右子是否存在}
    M --> N
    N -- 是 --> O(右子入队)
    N -- 否 --> P(继续下一次循环)
    O --> P
    P --> I
    I -- 循环结束 --> Q(将 current_level 存入总结果)
    Q --> E

五、 复杂度分析与优化建议

1. 时间复杂度：$O(N)$。每个节点访问且仅访问一次。在 NOI 竞赛中，如果 $N=10^5$，此算法依然能秒杀。
2. 空间复杂度：$O(N)$。主要开销是队列和存储结果的容器。
3. 优化建议：
   • 在 C++ 中，vector 的 push_back 会触发动态扩容，如果已知节点总数，可以先用 reserve() 预留空间。
   • 如果内存极其紧张，可以考虑使用两个 vector 交替存储当前层和下一层，而不是使用 std::queue。
   • NOI 避坑点：注意题目中是否有空树的情况（$n=0$），在代码开头必须特判，否则访问 root 指针会 Segment Fault。

六、 读题关键词（拿分关键）

在做树形结构题目时，要在题干中圈出这些词：

1. “从左到右”：决定了入队的顺序（先左后右）。
2. “层序”/“每一层”：暗示了需要记录当前队列的长度，或者使用 BFS 变种。
3. “返回其节点值”：注意返回值的数据类型，通常是 vector<vector<int>>。在 NOI 填空或大题中，注意输出格式（换行、空格）。

同学，现在的任务是：请不参考任何现成代码，尝试在你的编辑器上实现这个逻辑。记住，**控制好那个 size 变量是分层的关键！**加油。