你好！我是你的 OI 金牌教练。今天我们挑战二叉树构造系列的“终极篇”——根据前序和后序遍历构造二叉树。

这道题在 NOI 竞赛中属于中档偏基础的构造题。它与之前的“前中”或“中后”组合最大的不同点在于：前序+后序序列并不一定能唯一确定一棵二叉树（当某个节点只有一个子节点时，无法确定它是左孩子还是右孩子）。但题目要求我们只需输出任意一个满足条件的答案即可。

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

题目名称：根据前序和后序遍历构造二叉树 (construct_binary_tree_pre_post) 时间限制：1.0s 内存限制：256MB

【问题描述】 给定一棵二叉树的两个遍历序列：前序遍历 (preorder) 和 后序遍历 (postorder)。请你根据这两个序列构造出原二叉树并输出其中序遍历序列。 如果存在多个满足条件的二叉树，输出其中任意一个即可。

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

【输出格式】 输出一行，包含 $n$ 个整数，表示构造出的二叉树的中序遍历序列，整数之间用空格隔开。

【样例 1 输入】

7
1 2 4 5 3 6 7
4 5 2 6 7 3 1

【样例 1 输出】

4 2 5 1 6 3 7

【数据范围】

• $1 \le n \le 30$ （注：LeetCode 原题范围较小，NOI 练习中通常设为 $1000$ 以内）
• 每个节点的值各不相同，且在 $[1, n]$ 之间。
• preorder 和 postorder 互为二叉树的合法遍历序列。

二、 预备知识点

1. 前序遍历特性：第一个元素是根节点，第二个元素（如果存在）是左子树的根节点。
2. 后序遍历特性：最后一个元素是根节点，倒数第二个元素（如果存在）是右子树的根节点。
3. 区间分治：利用前序的“左根”在后序中的位置，划分出左子树和右子树的范围。
4. 递归构造：根据确定的范围递归建立物理连接。

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

请跟我一起在草稿纸上推演如何找到“分界点”：

1. 结构化拆解

• 前序序列：{ 根 | (左子树根) ... 左子树 | 右子树 }
• 后序序列：{ 左子树 | (左子树根) | 右子树 | 根 }

2. 推演过程

1. 确定当前根：前序的 preL。
2. 寻找左子树根：如果是叶子节点（preL == preR），直接返回。否则，前序的 preL + 1 就是左子树的根。
3. 确定规模：在后序序列中找到这个“左子树根”的位置 idx。
4. 从后序序列的开头到 idx 的这段区间，就是整个左子树。
5. 计算左子树大小：size = idx - postL + 1。

3. 复杂度与优化

• 时间复杂度：$O(N^2)$ 暴力搜索索引，或 $O(N)$ 使用哈希表预存索引。由于 $N$ 较小，重点应放在递归逻辑的正确性上。
• 空间复杂度：$O(N)$ 存储树结构及递归栈。

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

在 NOI 竞赛中，使用索引范围 (preL, preR, postL, postR) 来控制递归是最稳健的做法。

graph TD
    Start(开始 Build 子树) --> RangeCheck{preL 是否大于 preR}
    RangeCheck -- 是 --> ReturnNull(返回空节点编号)
    RangeCheck -- 否 --> CreateRoot(根节点 id 为 preL)
    CreateRoot --> SingleNode{preL 是否等于 preR}
    SingleNode -- 是 --> ReturnID(返回当前节点编号)
    SingleNode -- 否 --> FindLeftRoot(左子树根的值为 pre 的 preL加1)
    FindLeftRoot --> LocateIdx(在 post 序列中查到该值的下标为 idx)
    LocateIdx --> CalcSize(左子树大小 size 为 idx 减 postL 加 1)
    
    subgraph RecurSplit (递归切分区间)
        L_Child(左子树: 前序 preL加1 到 preL加size, 后序 postL 到 idx)
        R_Child(右子树: 前序 preL加size加1 到 preR, 后序 idx加1 到 postR减1)
    end
    
    CalcSize --> L_Child
    L_Child --> R_Child
    R_Child --> Connect(连接左右孩子并返回根节点)

五 : 时间复杂度优化建议与思考

1. 索引映射：在递归之前，先用一个全局数组 pos[N] 记录后序遍历中每个元素的位置。这样 LocateIdx 的操作就可以从 $O(N)$ 降到 $O(1)$，总复杂度达到 $O(N)$。
2. 静态内存：在 C++14 竞赛中，使用 int L[MAXN], R[MAXN] 代替结构体指针可以提高运行常数，且避免 new 带来的内存管理风险。
3. 中序验证：构造完成后，进行一次简单的 DFS 即可输出中序序列。

六 : 关键读题关键词

1. "前序和后序" (Pre & Post)：这是解题核心。要警惕它不像“前中”那样能唯一确定结构。
2. "任意一个" (Any)：在递归中，当我们取 pre[preL + 1] 作为左子树根时，实际上是默认了如果只有一个孩子，就把它当作左孩子。
3. "每个节点值不同"：这是建立 pos 映射表的安全保障。
4. "返回中序遍历"：这是本题的输出要求，不要直接返回树结构。

教练寄语： 这道题是二叉树重构系列中最灵活的一题。重点在于理解区间长度的守恒性——无论在前序还是后序中，同一棵子树所占的节点个数必须是相等的。算准了 size，你就拿到了满分的钥匙！加油！