你好，同学。很高兴能带你一起攻克这道关于树结构的基础题目。在 NOI 竞赛中，树的遍历是所有图论和树形 DP 的根基。虽然 LeetCode 上的这道题看似简单，但我们要从“算法竞赛”的角度去深挖它的本质。

---

一、 预备知识点

在挑战此题前，请确保你已掌握：

1. 树的存储结构：链式前向星或 std::vector<int> adj[]（邻接表）。
2. 递归与 DFS：理解函数调用栈的原理。
3. 栈 (Stack) 的性质：后进先出 (LIFO)，如何用栈模拟递归。
4. C++ STL：熟练使用 std::vector 和 std::stack。

---

二、 题目描述 (NOI 竞赛格式)

题目名称：N 叉树的前序遍历 (n-ary-tree-preorder-traversal)

【问题描述】 给定一个 $N$ 叉树的根节点，请你输出该树的前序遍历结果。 $N$ 叉树的前序遍历定义为：首先访问根节点，然后按照从左到右的顺序依次对每一棵子树进行前序遍历。

【输入格式】 第一行包含一个整数 $n$，表示节点总数。 接下来的 $n$ 行，每行描述一个节点的信息： 首先是一个整数 $v$ 表示该节点的值，接着是一个整数 $k$ 表示子节点数量，随后是 $k$ 个整数，表示该节点对应的子节点编号（编号从 $0$ 到 $n-1$）。 根节点编号固定为 $0$。

【输出格式】 输出一行，包含 $n$ 个由空格隔开的整数，表示前序遍历的序列。

【样例输入】

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

(注：对应逻辑结构为：1是根，有3个孩子3,2,4；3有两个孩子5,6...以此类推)

【样例输出】

1 3 5 6 2 4

【数据规模与约定】

• $0 \le n \le 10^4$
• $0 \le \text{node.val} \le 10^4$
• 树的高度不超过 $10^3$。

---

三、 教学启发与草稿纸推演

1. 启发式思考：何为“前序”？

想象你是一名探险家，要进入一个多层的地宫（树）。

• 规则一：每到一个新房间，先在笔记本上记录这个房间的宝藏值。
• 规则二：如果房间里有多个门（子节点），永远从左手边第一个门开始进。
• 规则三：只有探索完左边门里所有的密室，才能回到这个房间进右边的门。

这就是递归的思想。

2. 草稿纸推演过程

请你在草稿纸上画出一个简单的 3 叉树：

      A
    / | \
   B  C  D
  / \
 E   F

步骤：

1. 访问 A，写下 A。
2. 发现 A 有孩子 {B, C, D}。按顺序先去 B。
3. 访问 B，写下 B。
4. 发现 B 有孩子 {E, F}。按顺序先去 E。
5. 访问 E，写下 E。E 无孩子，回退到 B。
6. 去 B 的下一个孩子 F。写下 F，回退。
7. B 探索完了，回到 A。去 A 的下一个孩子 C...

结论：递归的本质是利用系统栈自动帮我们记录“接下来该去哪”。

3. 进阶：如何不用递归（迭代法）？

如果树的高度达到 $10^6$，递归会导致栈溢出（Runtime Error）。我们需要手动维护一个 std::stack。 关键推导：栈是后进先出。为了让左孩子先出栈，我们应该反向压入孩子。

• 压入 A。
• 弹出 A，将 A 的孩子 {B, C, D} 从右往左压入：先压 D，再压 C，最后压 B。
• 这样下次弹出的就是 B（最左边的孩子）。

---

四、 算法思路流程图 (Mermaid 风格)

方案 A：递归实现 (Recursive)

graph TD
    Start(开始 DFS 节点 u) --> CheckNull{u 是否为空}
    CheckNull -- 是 --> Return(返回)
    CheckNull -- 否 --> Record(记录 u 的值到结果数组)
    Record --> LoopStart(遍历 u 的所有子节点 v)
    LoopStart --> CallDFS(递归调用 DFS 节点 v)
    CallDFS --> LoopStart
    LoopStart -- 遍历结束 --> End(结束)

方案 B：迭代实现 (Iterative)

graph TD
    Start(开始) --> PushRoot(将根节点压入栈 S)
    PushRoot --> While{栈 S 是否为空}
    While -- 否 --> Pop(弹出栈顶节点 u)
    Pop --> Record(记录 u 的值到结果数组)
    Record --> GetChildren(获取 u 的所有子节点)
    GetChildren --> ReversePush(将子节点按从右到左顺序压入栈 S)
    ReversePush --> While
    While -- 是 --> End(结束)

---

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

1. 时间复杂度：

• 每个节点仅被访问一次。
• 对于每个节点，我们需要遍历其所有子节点。
• 总复杂度为 $O(N)$，其中 $N$ 为节点总数。在 NOI 竞赛中，10^4 的规模通常要求在 1ms-10ms 内完成，此算法完全达标。

2. 空间复杂度：

• 递归版：取决于搜索深度（树的高度 $H$），最坏情况 $O(N)$（退化成链），平均 $O(\log N)$。
• 迭代版：栈中最多存储 $O(N)$ 个节点。

3. 优化建议：

• 在 C++ 中，如果 vector 频繁扩容会耗时，建议在开始遍历前使用 ans.reserve(n) 预分配内存。
• 读入大规模数据时，使用 scanf 或 cin.tie(0) 加快 I/O。

---

六、 读题关键词总结

在 NOI 题目中，看到以下词汇要迅速反应：

1. “前序/后序/层序”：暗示了 DFS 或 BFS 的遍历顺序。
2. “N 叉树”：意味着不能只写 left 和 right 指针，要用 vector 或链式前向星存边。
3. “从左到右”：决定了你递归遍历子节点的顺序，或者迭代时压栈的顺序（反向压栈）。
4. “迭代实现”：如果题目补充要求不使用递归，考点就是栈模拟。

希望这些启发对你有帮助！在草稿纸上模拟一遍那个反向压栈的过程，你会对“栈”有更深刻的理解。加油！