用C++写一段根据后序和中序遍历输出先序遍历的程序

以下是用 C++ 编写的根据后序和中序遍历输出先序遍历的程序：

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

unordered_map<int, int> inorder_map;

vector<int> getPreorder(vector<int>& inorder, vector<int>& postorder, int in_start, int in_end, int post_start, int post_end) {
    if (in_start > in_end) {
        return {};
    }
    int root_val = postorder[post_end];
    int root_index = inorder_map[root_val];
    int left_size = root_index - in_start;
    vector<int> left_preorder = getPreorder(inorder, postorder, in_start, root_index - 1, post_start, post_start + left_size - 1);
    vector<int> right_preorder = getPreorder(inorder, postorder, root_index + 1, in_end, post_start + left_size, post_end - 1);
    vector<int> preorder;
    preorder.push_back(root_val);
    preorder.insert(preorder.end(), left_preorder.begin(), left_preorder.end());
    preorder.insert(preorder.end(), right_preorder.begin(), right_preorder.end());
    return preorder;
}

vector<int> buildPreorder(vector<int>& inorder, vector<int>& postorder) {
    int n = inorder.size();
    for (int i = 0; i < n; ++i) {
        inorder_map[inorder[i]] = i;
    }
    return getPreorder(inorder, postorder, 0, n - 1, 0, n - 1);
}

int main() {
    vector<int> inorder = {4, 2, 5, 1, 3};
    vector<int> postorder = {4, 5, 2, 3, 1};
    vector<int> preorder = buildPreorder(inorder, postorder);
    for (int i = 0; i < preorder.size(); ++i) {
        cout << preorder[i] << " ";
    }
    cout << endl;
    return 0;
}

程序中使用了哈希表来存储中序遍历中每个元素的下标，以便在递归中快速查找根节点的下标。实现方法是，传入中序遍历、后序遍历、中序遍历的起始和终止下标、后序遍历的起始和终止下标，找到当前的根节点，然后分别递归左子树和右子树，最后将根节点和左右子树的先序遍历合并即可。

运行程序，输出结果为：1 2 4 5 3。

希望可以帮助到您！