给定二叉树的中序和后序排列确定二叉树的前序排列C++

可以通过递归的方式来确定二叉树的前序排列。

首先，我们可以观察到，二叉树的后序排列的最后一个元素一定是根节点。

然后，我们在中序排列中找到根节点的位置，根节点左边的元素一定是左子树的节点，根节点右边的元素一定是右子树的节点。

接下来，我们可以根据中序排列中根节点的位置，将后序排列划分成左子树的后序排列和右子树的后序排列。

然后，我们可以递归地对左子树和右子树进行相同的操作，直到只剩下一个节点或者没有节点。

最后，我们可以将根节点放在前序排列的第一个位置，然后将左子树的前序排列依次放在根节点后面，再将右子树的前序排列依次放在左子树的前序排列后面。

下面是一个示例代码：

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

vector<int> preOrder(vector<int>& inorder, vector<int>& postorder) {
    if (inorder.empty() || postorder.empty()) {
        return {};
    }
    
    int rootVal = postorder.back();
    vector<int>::iterator rootPos = find(inorder.begin(), inorder.end(), rootVal);
    
    vector<int> leftInorder(inorder.begin(), rootPos);
    vector<int> rightInorder(rootPos + 1, inorder.end());
    
    vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
    vector<int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end() - 1);
    
    vector<int> leftPreorder = preOrder(leftInorder, leftPostorder);
    vector<int> rightPreorder = preOrder(rightInorder, rightPostorder);
    
    vector<int> preorder;
    preorder.push_back(rootVal);
    preorder.insert(preorder.end(), leftPreorder.begin(), leftPreorder.end());
    preorder.insert(preorder.end(), rightPreorder.begin(), rightPreorder.end());
    
    return preorder;
}

int main() {
    vector<int> inorder = {4, 2, 5, 1, 3};
    vector<int> postorder = {4, 5, 2, 3, 1};
    
    vector<int> preorder = preOrder(inorder, postorder);
    
    for (int val : preorder) {
        cout << val << " ";
    }
    cout << endl;
    
    return 0;
}

输出结果为：1 2 4 5