你好，同学。在掌握了前序遍历的“根-左-右”逻辑后，今天我们要攻克的是二叉树的中序遍历。

在 NOI 竞赛中，中序遍历（Inorder Traversal）具有极其特殊的地位：它是**二叉搜索树（BST）**的灵魂。对于一棵 BST，其中序遍历序列必然是单调递增的。理解中序遍历的多种实现，是后续学习平衡树（Treap, Splay, AVL）以及树上启发式合并（DSU on Tree）的必经之路。

---

一、 题目描述 (NOI 风格)

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

【问题描述】 给定一棵拥有 $n$ 个节点的二叉树，请输出该二叉树的中序遍历序列。 中序遍历的顺序为：左子树 -> 根节点 -> 右子树。

在算法竞赛中，虽然递归是最简单的实现方式，但为了应对超大规模数据及极端内存限制，你必须熟练掌握基于显式栈的迭代法，以及空间复杂度为 $O(1)$ 的 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 3 2

【数据范围】

• 树中节点数目 $n$ 范围是 $[0, 100]$。
• $-100 \le Node.val \le 100$。
• 进阶要求：必须掌握递归、迭代（显式栈）及 Morris 遍历三种算法。

---

二、 预备知识点

1. 中序遍历定义：左子树处理完，才处理根，最后处理右子树。
2. 栈 (Stack) 的回溯性质：利用栈记录“路过的根”，以便从左子树回来时能找到它。
3. Morris 遍历 (线索化)：利用叶子节点的空右指针指向其后继节点，实现无栈回溯。

---

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

请拿出草稿纸，我们来看看中序遍历的逻辑演流。

1. 递归思维 (由深至浅)

中序遍历像是一个“左侧优先”的深度搜索：

• 只要有左边，就一直往左钻。
• 钻不动了（左边为空），记录当前位置。
• 然后尝试往右边迈一步。

2. 迭代思维 (路标模型)

在迭代时，我们需要一个指针 curr 和一个栈。

• 推演过程：
  1. curr 只要不为空，就把它压入栈中（它是一个“待处理”的根），然后 curr = curr->left。
  2. 当 curr 钻到头了，从栈里弹出一个节点。
  3. 关键时刻：这个弹出的节点就是最左边的根，输出它。
  4. 然后把 curr 移向这个节点的右孩子，继续重复上述逻辑。

3. Morris 遍历 (时空折叠)

中序遍历的 Morris 算法与前序唯一的区别在于访问时机：

• 逻辑：当你发现一个节点有左子树时，去左子树找它的“前驱”（左子树最右边的点）。
• 建立线索：如果前驱的右指针为空，说明还没处理左子树，建立指向当前根的线索，去左子树。
• 访问与回溯：如果前驱的右指针已经指向自己，说明左子树已经遍历完了。此时访问当前根，拆掉线索，去右子树。

---

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

1. 递归法逻辑

graph TD
    A("递归开始 Inorder(node)") --> B{"node 是否为空?"}
    B -- "是" --> C["直接返回"]
    B -- "否" --> D["1. 递归调用 Inorder(node 乘 left)"]
    D --> E["2. 访问并记录 node 乘 val"]
    E --> F["3. 递归调用 Inorder(node 乘 right)"]
    F --> G["返回"]

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

graph TD
    Start("开始") --> Init["curr 等于 root, 准备栈 S"]
    Init --> Loop{"curr 非空 OR 栈 S 非空?"}
    Loop -- "是" --> GoLeft{"curr 是否非空?"}
    GoLeft -- "是 (一路向左)" --> Push["1. 将 curr 压入栈 S <br> 2. curr 等于 curr 乘 left"]
    Push --> GoLeft
    GoLeft -- "否 (触底反弹)" --> Pop["1. 从栈 S 弹出节点 t <br> 2. 访问 t 乘 val <br> 3. curr 等于 t 乘 right"]
    Pop --> Loop
    Loop -- "否" --> End("结束")

3. Morris 遍历逻辑

graph TD
    M1("开始") --> M2{"curr 是否为空?"}
    M2 -- "否" --> M3{"curr 有左孩子吗?"}
    M3 -- "无" --> M4["1. 访问 curr 乘 val <br> 2. curr 等于 curr 乘 right"]
    M4 --> M2
    M3 -- "有" --> M5["找到左子树最右节点 pre"]
    M5 --> M6{"pre 乘 right 为空?"}
    M6 -- "是 (建立线索)" --> M7["1. pre 乘 right 等于 curr <br> 2. curr 等于 curr 乘 left"]
    M7 --> M2
    M6 -- "否 (拆除线索)" --> M8["1. pre 乘 right 等于 NULL <br> 2. 访问 curr 乘 val <br> 3. curr 等于 curr 乘 right"]
    M8 --> M2
    M2 -- "是" --> M9("结束")

---

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

• 时间复杂度：
  • 三种方法均为 $O(n)$。Morris 遍历中每条边最多被访问 2 次。
• 空间复杂度：
  • 递归/迭代：$O(h)$，$h$ 为树高。极端情况下（退化为链）为 $O(n)$。
  • Morris：$O(1)$。在 NOI 题目中，如果内存限制在 16MB 以内，Morris 是必杀技。

优化建议：

1. 递归深度：在处理深度超过 $10^5$ 的树时，NOI 默认栈空间可能不足。建议优先使用迭代法。
2. 静态存储：在 C++ 中，频繁 new 节点会变慢。使用 struct tree[MAXN] 数组存储节点是竞赛中的常态。
3. Morris 适用性：注意 Morris 会修改树的 right 指针，虽然最后会改回来，但在多线程或只读场景下不可用（竞赛中通常不考虑此点）。

---

六、 读题关键词总结

1. “中序 (Inorder)”：核心在于“中间访问”。如果你在处理二叉搜索树，看到这个词就等同于看到了“有序序列”。
2. “不改变树结构”：这是 Morris 遍历的注意点，虽然它过程中改变了，但必须保证退出函数时树已复原。
3. “左、根、右”：在画图分析时，中序遍历相当于从树的正上方往下投影得到的顺序。

教练寄语： 中序遍历是树结构中最具“顺序美感”的遍历。递归法展示了分治，迭代法展示了状态回溯，而 Morris 遍历则展示了人类对空间利用的极致想象力。请你在草稿纸上分别画出一棵 3 层的满二叉树，用这三种方法走一遍流程，你会对“指针”有全新的认识。加油！