在第 4.3.4 节中，我们学习了中序遍历与后序遍历结合重构二叉树的算法原理。

题目

给定两个整数数组 inorder 和 postorder，其中 inorder 是二叉树的中序遍历，postorder 是同一棵树的后序遍历（节点值各不相同），请构造二叉树并分别输出其前序遍历与层序遍历。

输入格式

• 第一行：节点总数 $n$；
• 第二行：$n$ 个整数，表示中序遍历；
• 第三行：$n$ 个整数，表示后序遍历。

输出格式

• 第一行：PREORDER: 后跟空格分隔的前序遍历序列；
• 第二行：LEVELORDER: 后跟空格分隔的层序遍历序列。

样例

样例输入 1

5
9 3 15 20 7
9 15 7 20 3

样例输出 1

PREORDER: 3 9 20 15 7
LEVELORDER: 3 9 20 15 7

样例输入 2

4
4 3 2 1
4 3 2 1

样例输出 2

PREORDER: 1 2 3 4
LEVELORDER: 1 2 3 4

样例输入 3

1
1
1

样例输出 3

PREORDER: 1
LEVELORDER: 1

如何验证

先安装 Node.js、pnpm 和支持 C++17 的编译器。GNU Make 是首选入口，但不是强制依赖。

# 已进入本 Lab 目录
make doctor
make run
make run CASE=001-sample
make interactive
make score

Windows 没有安装 Make 时，在仓库根目录使用完全相同的评分内核：

pnpm lab:doctor -- labs/chapter-04/exercise/E-04-07-construct-binary-tree-in-post
pnpm lab:run -- labs/chapter-04/exercise/E-04-07-construct-binary-tree-in-post
pnpm lab:run -- labs/chapter-04/exercise/E-04-07-construct-binary-tree-in-post --case 001-sample
pnpm lab:score -- labs/chapter-04/exercise/E-04-07-construct-binary-tree-in-post

make run 在答案尚未全对时仍正常返回，避免 Make 把学习结果显示成工具故障；make score 是严格入口，只有 100 分才返回成功。标准输出参与判题，调试信息请写入标准错误。

题解

点击查看题解

核心思路

与前序+中序恢复对称：

1. 后序遍历的最后一个元素 postorder[postR] 必定是当前子树的根节点；
2. 利用哈希表找到根节点在中序序列中的位置 inRoot；
3. 左子树大小 leftSize = inRoot - inL；
4. 后序中左子树区间为 [postL, postL + leftSize - 1]，右子树区间为 [postL + leftSize, postR - 1]；
5. 递归求解。

复杂度分析

• 时间复杂度：$O(n)$。
• 空间复杂度：$O(n)$。

点击查看参考代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>

struct TreeNode {
    int val = 0;
    TreeNode* left = nullptr;
    TreeNode* right = nullptr;

    TreeNode() = default;
    TreeNode(int x) : val(x) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

TreeNode* helper(const std::vector<int>& inorder, int inL, int inR,
                 const std::vector<int>& postorder, int postL, int postR,
                 const std::unordered_map<int, int>& inMap) {
    if (inL > inR || postL > postR) return nullptr;
    int rootVal = postorder[postR];
    TreeNode* root = new TreeNode(rootVal);
    int inRoot = inMap.at(rootVal);
    int leftSize = inRoot - inL;
    root->left = helper(inorder, inL, inRoot - 1, postorder, postL, postL + leftSize - 1, inMap);
    root->right = helper(inorder, inRoot + 1, inR, postorder, postL + leftSize, postR - 1, inMap);
    return root;
}

TreeNode* buildTree(const std::vector<int>& inorder, const std::vector<int>& postorder) {
    std::unordered_map<int, int> inMap;
    for (int i = 0; i < (int)inorder.size(); i++) {
        inMap[inorder[i]] = i;
    }
    return helper(inorder, 0, (int)inorder.size() - 1, postorder, 0, (int)postorder.size() - 1, inMap);
}

void preorder(TreeNode* root, std::vector<int>& res) {
    if (!root) return;
    res.push_back(root->val);
    preorder(root->left, res);
    preorder(root->right, res);
}

std::vector<int> levelorder(TreeNode* root) {
    std::vector<int> res;
    if (!root) return res;
    std::queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* cur = q.front();
        q.pop();
        res.push_back(cur->val);
        if (cur->left) q.push(cur->left);
        if (cur->right) q.push(cur->right);
    }
    return res;
}

void freeTree(TreeNode* root) {
    if (!root) return;
    freeTree(root->left);
    freeTree(root->right);
    delete root;
}

int main() {
    int n;
    if (!(std::cin >> n) || n <= 0) return 0;
    std::vector<int> inorder(n), postorder(n);
    for (int i = 0; i < n; i++) std::cin >> inorder[i];
    for (int i = 0; i < n; i++) std::cin >> postorder[i];

    TreeNode* root = buildTree(inorder, postorder);

    std::vector<int> pre;
    preorder(root, pre);
    std::cout << "PREORDER:";
    for (int v : pre) std::cout << " " << v;
    std::cout << "\n";

    std::vector<int> lvl = levelorder(root);
    std::cout << "LEVELORDER:";
    for (int v : lvl) std::cout << " " << v;
    std::cout << "\n";

    freeTree(root);
    return 0;
}