你好！我是你的 OI 金牌教练。今天我们来攻克二叉树重构中的另一个核心问题——从中序与后序遍历序列还原二叉树。

这道题是前序+中序还原的姊妹篇，在 NOI 竞赛中，它考察的是你对递归边界的精细控制能力以及对**后序遍历结构（左-右-根）**的深刻理解。

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

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

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

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

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

【样例 1 输入】

5
9 3 15 20 7
9 15 7 20 3

【样例 1 输出】

3 9 20 15 7

【样例 2 输入】

1
-1
-1

【样例 2 输出】

-1

【数据范围】

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

二、 预备知识点

1. 后序遍历特性：序列的最后一个元素永远是当前子树的根节点。
2. 中序遍历特性：根节点将序列划分为左、右两部分。左侧是左子树，右侧是右子树。
3. 子树规模一致性：同一棵子树，其在中序序列和后序序列中所占的**节点数量（长度）**是完全相等的。
4. 哈希/索引加速：使用全局数组记录中序序列中各值的位置，避免重复扫描。

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

请在纸上模拟还原过程，这能帮你理清最难处理的“区间坐标”：

1. 结构化拆解

• 后序序列：[ 左子树节点 | 右子树节点 | 根节点 ]
• 中序序列：[ 左子树节点 | 根节点 | 右子树节点 ]

2. 推导步骤 (以样例 1 为例)

1. 看后序末尾：3 是根。
2. 在中序中找 3：位置在索引 1。
3. 计算规模：
   • 中序中 3 的左边是 [9]，规模为 1。
   • 中序中 3 的右边是 [15, 20, 7]，规模为 3。
4. 切割区间：
   • 左子树：后序中拿前 1 个元素 [9]，中序中拿 [9]。
   • 右子树：后序中拿中间 3 个元素 [15, 7, 20]，中序中拿 [15, 20, 7]。
5. 递归：对左右子树重复上述过程。

3. 复杂度分析思考

• 时间复杂度：若使用 $O(1)$ 索引查找，每个节点被处理一次，总复杂度 $O(N)$。
• 空间复杂度：由于需要静态存储树结构和递归深度，复杂度为 $O(N)$。

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

在 NOI 竞赛中，我们通常手动管理数组区间。注意后序遍历的根在 postR。

graph TD
    Start(开始构建 Build_Subtree) --> RangeCheck{区间是否合法 inL 大于 inR}
    RangeCheck -- 是 --> ReturnEmpty(返回空节点标识)
    RangeCheck -- 否 --> GetRoot(后序序列 postR 位置是当前根节点值)
    GetRoot --> FindIn(在中序索引表中查到根的索引 k)
    FindIn --> CalcSize(左子树规模 size 等于 k 减 inL)
    
    subgraph SplitLogic [核心逻辑：子树区间划分]
        L_In(左中序: inL 到 k-1)
        L_Post(左后序: postL 到 postL加size减1)
        R_In(右中序: k加1 到 inR)
        R_Post(右后序: postL加size 到 postR减1)
    end
    
    CalcSize --> L_In
    L_In --> L_Post
    L_Post --> R_In
    R_In --> R_Post
    
    R_Post --> RecurL(递归构建左子树)
    RecurL --> RecurR(递归构建右子树)
    RecurR --> Finish(返回当前根节点编号)

五、 关键读题关键词与易错点

1. "后序" (Postorder)：根在末尾。易错点：递归划分右子树时，后序区间的右边界是 postR - 1，千万别把当前的根又包进去。
2. "节点值各不相同"：这是使用哈希索引（pos[val]）的前提。如果节点值范围很大（如 $10^9$），请使用 std::map 或离散化。
3. "右子树优先？"：在某些高级迭代算法中，由于后序的倒序是“根-右-左”，先处理右子树会更方便。但标准递归写法无需纠结顺序。
4. 数据范围 $3000$：
   • 空间建议：在 C++14 中，建议使用静态数组 int L[3005], R[3005] 存储树结构，避免频繁 new 对象。
   • 时间建议：$O(N)$ 或 $O(N \log N)$ 均可满分，但 $O(N^2)$ 在大规模测试下可能危险。

教练总结

解题口诀：

• 前中还原：前序找头，中序分家，左子紧跟。
• 中后还原：后序找尾，中序分家，右子托后。

记住：**规模（Size）**是连接中序序列和后序序列的唯一桥梁。只要算准了左子树有多少个节点，你就永远不会切错区间！现在，请在草稿纸上推演一下，当左子树规模为 0 时，你的区间公式是否依然有效？加油！