我们知道如何按照三种深度优先次序来周游一棵二叉树，来得到中根序列、前根序列和后根序列。反过来，如果给定二叉树的中根序列和后根序列，或者给定中根序列和前根序列，可以重建一二叉树。本题输入一棵二叉树的中根序列和后根序列，要求在内存中重建二叉树，最后输出这棵二叉树的前根序列。 用不同的整数来唯一标识二叉树的每一个结点，下面的二叉树 中根序列是9 5 32 67 后根序列9 32 67 5 前根序列5 9 67 32 输入 两行。第一行是二叉树的中根序列，第二行是后根序列。每个数字表示的结点之间用空格隔开。结点数字范围0～65535。暂不必考虑不合理的输入数据。 输出 一行。由输入中的中根序列和后根序列重建的二叉树的前根序列。每个数字表示的结点之间用空格隔开。 样例输入 9 5 32 67 9 32 67 5 样例输出 5 9 67 32。C++实现

以下是 C++ 代码实现：

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

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder, int in_left, int in_right, int post_left, int post_right, unordered_map<int, int>& inorder_map) {
    if (in_left > in_right || post_left > post_right) {
        return nullptr;
    }
    int root_val = postorder[post_right];
    auto root = new TreeNode(root_val);
    int in_root = inorder_map[root_val];
    int left_size = in_root - in_left;
    root->left = buildTree(inorder, postorder, in_left, in_root - 1, post_left, post_left + left_size - 1, inorder_map);
    root->right = buildTree(inorder, postorder, in_root + 1, in_right, post_left + left_size, post_right - 1, inorder_map);
    return root;
}

vector<int> preorderTraversal(TreeNode* root) {
    vector<int> res;
    if (root == nullptr) {
        return res;
    }
    res.push_back(root->val);
    auto left = preorderTraversal(root->left);
    res.insert(res.end(), left.begin(), left.end());
    auto right = preorderTraversal(root->right);
    res.insert(res.end(), right.begin(), right.end());
    return res;
}

vector<int> buildTree(vector<int>& inorder, vector<int>& postorder) {
    int n = inorder.size();
    unordered_map<int, int> inorder_map;
    for (int i = 0; i < n; i++) {
        inorder_map[inorder[i]] = i;
    }
    auto root = buildTree(inorder, postorder, 0, n - 1, 0, n - 1, inorder_map);
    return preorderTraversal(root);
}

int main() {
    vector<int> inorder = {9, 5, 32, 67};
    vector<int> postorder = {9, 32, 67, 5};
    auto res = buildTree(inorder, postorder);
    for (int x : res) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

时间复杂度为 $O(n)$，其中 $n$ 为二叉树的节点数。