你好！我是你的 OI 教练。今天我们要探讨的是树论中的基础必考模型——N叉树的层序遍历。

在 NOI 竞赛中，层序遍历不仅是 BFS（广度优先搜索）的直接应用，更是处理“按层分析”类动态规划（树形 DP）或计算树的宽度、直径等问题的核心工具。

一、 题目描述 (NOI 规范)

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

【问题描述】 给定一个 $N$ 叉树的根节点 $root$，请你返回其节点值的层序遍历。层序遍历即逐层地、从左到右访问所有节点。 要求输出结果必须体现出“层”的结构，即每一层的节点应当被分别归类。

【输入格式】 输入文件包含多行，描述树的结构： 第一行一个整数 $n$，表示节点总数。 接下来的 $n$ 行，每行描述一个节点：首先是该节点的值 $v$，然后是该节点的子节点数量 $k$，最后是 $k$ 个子节点的编号。 （注：编号从 0 到 $n-1$，根节点固定为 0。如果 $n=0$ 则树为空。）

【输出格式】 第一行输出一个整数 $L$，表示树的总深度（层数）。 接下来输出 $L$ 行，每行包含该层的所有节点值，值之间用空格隔开。

【样例 1 输入】

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

【样例 1 输出】

3
1
3 2 4
5 6

【样例 2 输入】

14
1 4 1 2 3 4
2 0
3 2 5 6
4 1 7
5 2 8 9
6 0
7 1 10
8 1 11
9 1 12
10 0
11 1 13
12 0
13 0
14 0

【样例 2 输出】

5
1
2 3 4 5
6 7 8 9 10
11 12 13
14

【数据范围】

• 节点总数 $0 \le n \le 10^4$
• 树的深度 $\le 1000$

二、 预备知识点

1. 广度优先搜索 (BFS)：利用队列先进先出的特性，按距离起点的步数（层数）向外扩张。
2. 队列 (std::queue)：用于存储待访问的节点。
3. 层级控制 (Level Processing)：如何区分当前节点属于哪一层。通常在进入下一层前，先记录当前队列的大小 size。
4. 树的存储：邻接表 vector<int> adj[N] 或结构体数组。

三、 启发式思维导图：草稿纸上的推演

请在草稿纸上跟我一起画出 BFS 的执行轨迹：

1. 核心矛盾：如何“分层”？

普通的 BFS 会一股脑地把节点放进队列，但这题要求按层输出。 技巧：在处理每一层之前，队列里的元素恰好全部属于这一层。

• 记录当前队列长度 len = q.size()。
• 连续弹出 len 个节点，它们都属于当前层。
• 它们产生的所有孩子，会自动排在队列后方，成为“下一层”。

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

• 时间复杂度：每个节点入队一次、出队一次。对于 $N$ 个节点，复杂度为 $O(N)$。在 $10^4$ 量级下，远低于 1s 限制。
• 空间复杂度：
  • 存储树：$O(N)$。
  • 队列空间：最坏情况下（树呈放射状），队列需要存储 $N-1$ 个节点，空间 $O(N)$。

3. 性能优化建议

• 避免频繁内存分配：在 NOI 比赛中，如果 $N$ 较大（如 $10^6$），可以使用 std::vector::reserve 预分配每层结果的空间。
• 快读：虽然 $10^4$ 没必要，但在 $10^5$ 量级以上建议使用 scanf 或 getchar 读入。

四、 算法思路提示 (伪代码流程图)

在 NOI 竞赛中，层序遍历的迭代写法（队列法）是标准解法。

graph TD
    Start(开始) --> CheckEmpty{n 是否为 0}
    CheckEmpty -- 是 --> End(结束)
    CheckEmpty -- 否 --> Init(初始化队列 Q 并将根节点 0 入队)
    Init --> WhileQ{Q 是否为空}
    WhileQ -- 否 --> GetSize(当前层节点数 sz = Q.size)
    GetSize --> LevelStart(准备存储当前层结果)
    LevelStart --> ForLoop(循环 sz 次)
    ForLoop --> Pop(弹出队首节点 u)
    Pop --> Save(记录 u 的值到当前层)
    Save --> ChildLoop(遍历 u 的所有子节点 v)
    ChildLoop --> Push(将 v 入队 Q)
    Push --> ChildLoop
    ChildLoop -- 遍历完子节点 --> ForLoop
    ForLoop -- 循环结束 --> StoreLevel(将当前层加入总结果 Res)
    StoreLevel --> WhileQ
    WhileQ -- 是 --> Output(输出层数和每层结果)
    Output --> End

五、 关键读题技巧：哪里是“解题钥匙”？

1. “层序” (Level Order)：
   • 看到这个词，脑子里立刻跳出 BFS 和 Queue。
2. “逐层地” (Level by level)：
   • 意味着你的 BFS 内部需要一个 while 嵌套 for 的结构，外层控层，内层控节点。
3. “N 叉” (N-ary)：
   • 提醒你子节点的个数是不确定的，遍历子节点时要使用 for(int v : adj[u]) 或 for(int i=0; i < k; i++)。
4. $n=0$ 的边界：
   • LeetCode 和 NOI 都会测试空输入。在 BFS 开始前，必须判断根节点是否存在，否则访问 adj[0] 或 q.push(root) 会引发运行时错误 (RE)。

教练寄语：层序遍历是后续学习“拓扑排序”和“最短路算法（Dijkstra/SPFA）”的母体。请务必熟练掌握 q.size() 这种分层技巧，这在处理带权树的层级 DP 时非常有用！加油！