你好，同学。在完成了链表的“三部曲”后，我们正式进入非线性数据结构的学习。今天我们要探讨的是二叉树的前序遍历。

在 NOI 竞赛中，树论是进阶算法（如线段树、树剖、LCT）的根基。而遍历算法则是你观察树结构的第一双眼睛。这道题看似简单，但它涵盖了从递归到栈模拟，再到极高阶的 Morris 遍历（空间 $O(1)$）的所有核心思想。

---

一、 题目描述 (NOI 风格)

【题目名称】 二叉树的前序遍历 (Binary Tree Preorder Traversal) 【时间限制】 1.0s 【内存限制】 256MB

【问题描述】 给你一棵二叉树的根节点 root，请你返回其节点值的前序遍历序列。 前序遍历的顺序为：根节点 -> 左子树 -> 右子树。

在 NOI 竞赛中，除了基本的递归实现，你还需要掌握如何使用显式栈（迭代法）来规避递归深度过大导致的栈溢出，以及如何在极度苛刻的空间限制下使用 Morris 遍历。

【输入格式】 第一行包含一个整数 $n$，表示节点总数。 接下来 $n$ 行，每行包含三个整数 $v, l, r$，分别表示编号为 $i$ ($1 \le i \le n$) 的节点的权值、左孩子编号和右孩子编号。若无孩子则为 $-1$。 （注：根节点默认为编号 1 的节点。）

【输出格式】 输出一行，包含 $n$ 个整数，表示前序遍历的结果。

【样例 1 输入】

3
1 -1 2
2 3 -1
3 -1 -1

【样例 1 输出】

1 2 3

【数据范围】

• 树中节点数目范围是 $[0, 100]$。
• $-100 \le Node.val \le 100$。
• 进阶要求：尝试使用迭代法与 Morris 遍历完成。

---

二、 预备知识点

1. 二叉树递归定义：理解每一个节点都可以看作是一棵子树的根。
2. 前序遍历逻辑：访问顺序是“自顶向下，先左后右”。
3. 栈 (Stack)：用于模拟递归过程中的系统调用栈。
4. 线索二叉树 (Threaded Binary Tree)：Morris 遍历的核心，利用叶子节点的空指针建立临时回溯路径。

---

三、 启发式教学：草稿纸上的推理过程

请拿出纸和笔，我们用三种思维模型来拆解这道题。

1. 递归思维 (最自然的逻辑)

想象你在森林里探险，每到一个路口（节点）：

1. 动作：在日记本上记下当前位置（访问根）。
2. 探索：先钻进左边的岔路（递归左子树）。
3. 探索：从左边回来后，再钻进右边的岔路（递归右子树）。

2. 迭代思维 (显式栈模拟)

由于栈是“后进先出 (LIFO)”，如果你想先访问左孩子，就必须先压入右孩子，再压入左孩子。

• 步骤：从栈中弹出一个节点 $u$ -> 记录 $u$ 的值 -> 把 $u$ 的非空右孩子压栈 -> 把 $u$ 的非空左孩子压栈。

3. Morris 遍历 (神级思维：空间 $O(1)$)

如何不使用栈也能回到父节点？

• 核心逻辑：利用左子树中最右侧节点的空指针。
• 操作：如果当前节点有左孩子，找到左子树中“最靠右”的节点，将其右指针指向当前节点（建立彩虹桥）。当你第二次通过这条桥回来时，说明左子树已遍历完，拆掉桥，去右边。

---

四、 算法流程图 (伪代码逻辑)

1. 递归法逻辑

graph TD
    A("开始 preorder(node)") --> B{"node 为空?"}
    B -- "是" --> C["直接返回"]
    B -- "否" --> D["1. 输出 node 的值"]
    D --> E["2. 递归调用 preorder(node 的左孩子)"]
    E --> F["3. 递归调用 preorder(node 的右孩子)"]
    F --> G["返回"]

2. 迭代法 (显式栈) 逻辑

graph TD
    A("开始") --> B["将 root 压入栈 S"]
    B --> C{"栈 S 是否为空?"}
    C -- "否" --> D["1. 弹出栈顶节点 curr"]
    D --> E["2. 输出 curr 的值"]
    E --> F["3. 如果 curr 的右孩子不为空, 则压入右孩子"]
    F --> G["4. 如果 curr 的左孩子不为空, 则压入左孩子"]
    G --> C
    C -- "是" --> H["结束"]

3. Morris 遍历逻辑

graph TD
    Start("开始") --> IsNull{"curr 为空?"}
    IsNull -- "否" --> HasLeft{"curr 有左孩子吗?"}
    HasLeft -- "无" --> VisitRight["1. 输出 curr 的值<br>2. curr 移向右孩子"]
    VisitRight --> IsNull
    
    HasLeft -- "有" --> FindPred["在左子树找 curr 的前驱节点 (predecessor)"]
    FindPred --> Bridge{"前驱的右孩子为空吗?"}
    
    Bridge -- "是 (建立彩虹桥)" --> Build["1. 前驱的右指针指向 curr<br>2. 输出 curr 的值<br>3. curr 移向左孩子"]
    Build --> IsNull
    
    Bridge -- "否 (拆掉彩虹桥)" --> Destroy["1. 前驱的右指针复原为 NULL<br>2. curr 移向右孩子"]
    Destroy --> IsNull
    
    IsNull -- "是" --> End("结束")

---

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

• 时间复杂度：
  • 三种方法均为 $O(n)$，因为每个节点都被访问了常数次（Morris 中每个边缘路径最多走两次）。
• 空间复杂度：
  • 递归法/迭代法：$O(h)$，其中 $h$ 为树的高度。在最坏情况下（树退化成链表），空间复杂度为 $O(n)$。
  • Morris 遍历：$O(1)$。这是算法竞赛中应对“极小内存限制”的杀手锏。

优化建议：

1. 防爆栈：在 NOI 中，若树深度达到 $10^5$ 级别，默认递归会爆栈。务必使用迭代法或通过 ulimit -s 增加栈空间（如果规则允许）。
2. Morris 警告：Morris 遍历虽然节省空间，但会暂时修改树结构。如果在遍历过程中需要并行读取树，或者树是只读的，这种方法不适用。

---

六、 读题关键词总结

在处理二叉树题目时，注意以下信号：

1. “前序/先序”：代表“根”要在“子”之前处理。常用于树的拷贝、构造、或者计算深度的预处理。
2. “迭代 (Iteratively)”：提示你不要使用简单的递归，考察对栈的理解。
3. “$O(1)$ 额外空间”：Morris 遍历的专属标签。
4. “节点数目范围 [0, n]”：再次提醒，一定要处理 空树 (root == nullptr) 的情况。在 NOI 考场上，空输入是常见的“挂分点”。

教练寄语： 二叉树的遍历是递归思想的第一个“试金石”。请务必在草稿纸上模拟 Morris 遍历中“桥”的建立与断开，理解了它，你就掌握了对树指针操作的最高控制力。加油！