你好！我是你的 OI 教练。今天我们要攻克的是树论中的核心经典问题——由遍历序列还原二叉树。

在 NOI 竞赛中，这不仅是考查递归思想的绝佳题目，更是理解树的形态与遍历逻辑之间“一一对应”关系的基石。

一、 题目描述 (NOI 规范版)

题目名称：从前序与中序遍历序列构造二叉树 (build_tree_pre_in) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一棵二叉树的两个遍历序列：前序遍历 (preorder) 和 中序遍历 (inorder)。请你根据这两个序列构造出原二叉树。 注意：假设树中没有重复的元素。

【输入格式】 输入文件包含三行。 第一行一个整数 $n$，表示二叉树的节点总数。 第二行包含 $n$ 个整数，表示二叉树的前序遍历序列。 第三行包含 $n$ 个整数，表示二叉树的中序遍历序列。

【输出格式】 输出一行，包含 $n$ 个整数，表示构造出的二叉树的后序遍历序列（作为还原正确性的验证），整数之间用空格隔开。

【样例 1 输入】

5
3 9 20 15 7
9 3 15 20 7

【样例 1 输出】

9 15 7 20 3

【样例 2 输入】

1
-1
-1

【样例 2 输出】

-1

【数据范围】

• $1 \le n \le 3000$
• 每个节点的值在 $[-3000, 3000]$ 之间。
• preorder 和 inorder 互为二叉树的合法遍历序列。
• 节点值各不相同。

二 : 预备知识点

1. 前序遍历特性：序列的第一个元素永远是当前子树的根节点。
2. 中序遍历特性：根节点将序列划分为左、右两个部分。左边是左子树的所有节点，右边是右子树的所有节点。
3. 分治与递归：利用上述特性，将大树的还原拆解为左子树的还原和右子树的还原。
4. 哈希映射优化：在寻找根节点在中序序列中的位置时，使用数组或 map 记录索引，将查询复杂度从 $O(n)$ 降至 $O(1)$。

三 : 启发式思维导图：教练的草稿纸

请拿起笔，在草稿纸上跟着我画出逻辑推理过程：

1. 核心发现

• 前序序列：[ 根 | 左子树所有节点 | 右子树所有节点 ]
• 中序序列：[ 左子树所有节点 | 根 | 右子树所有节点 ]

2. 推导步骤

1. 在前序序列中拿到第一个数，它就是当前的 Root。
2. 在中序序列中找到这个 Root 的位置，记为 idx。
3. 计算左子树的节点个数：left_size = idx - inorder_start。
4. 切割区间：
   • 左子树的前序区间：从当前根后面开始，数 left_size 个。
   • 左子树的中序区间：根的左边部分。
   • 右子树的前序区间：前序序列中左子树区间之后的所有数。
   • 右子树的中序区间：中序序列中根的右边部分。

3. 复杂度思考

• 时间复杂度：每个节点处理一次。如果在中序中查索引是 $O(1)$，则总复杂度 $O(n)$。
• 空间复杂度：由于需要存储树结构（或递归栈）以及索引映射，复杂度为 $O(n)$。

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

在 NOI 竞赛中，我们通常使用递归函数 build(preL, preR, inL, inR) 来表示当前需要还原的范围。

graph TD
    Start(开始构建 Build_Tree) --> RangeCheck{区间是否有效 preL 大于 preR}
    RangeCheck -- 是 --> ReturnNull(返回 空)
    RangeCheck -- 否 --> GetRoot(前序序列 preL 位置是当前根节点值)
    GetRoot --> FindIn(在中序序列中查到根节点的索引 k)
    FindIn --> CalcSize(计算左子树规模 size 等于 k 减 inL)
    
    subgraph RecursiveSteps [递归拆分]
        StepL(左子树区间: preL+1 到 preL+size, inL 到 k-1)
        StepR(右子树区间: preL+size+1 到 preR, k+1 到 inR)
    end
    
    CalcSize --> StepL
    CalcSize --> StepR
    StepL --> LinkL(递归构建左子树并连接)
    StepR --> LinkR(递归构建右子树并连接)
    LinkL --> Finish(返回当前根节点)
    LinkR --> Finish

五 : 时间复杂度优化建议

1. 快速索引：由于节点值唯一，建议在读入中序序列时，预处理一个 pos 数组或 unordered_map。例如 pos[val] = index。这样在递归时寻找 k 就不需要遍历。
2. 避免对象开辟：在 NOI 考场上，若内存受限，建议使用静态数组 L_child[N], R_child[N] 记录每个节点的左右孩子，而不是使用 new 创建对象。
3. 内联优化：还原过程是深度递归，确保递归边界处理清晰，且函数参数尽量精简。

六 : 关键读题关键词

1. "前序" (Preorder)：解题的切入点，提供“谁是根”的信息。
2. "中序" (Inorder)：解题的分割线，提供“谁在左，谁在右”的信息。
3. "不含重复元素"：这是算法的核心前提。如果有重复元素，中序分割将不唯一，树的形态也将不唯一。
4. "构造" (Construct)：意味着你需要建立物理上的连接关系，而不仅仅是输出序列。

教练寄语：这道题是递归结构的典范。理解了如何通过“前序定根、中序分左右”的套路，你就能轻松应对所有的遍历序列还原问题（比如中序+后序，或者中序+层序）。现在，去草稿纸上尝试写出区间的坐标变换公式吧！加油！