c++给出先序和中序 求后序 并把后序赋在一个数组上

在 C++ 中，如果你有一个二叉树，并且你知道其先序遍历 (Preorder) 和中序遍历 (Inorder)，你可以利用这些信息重建后序遍历 (Postorder)。由于中序遍历对于左、右子节点的顺序有明确的规定（根节点 -> 左子树 -> 右子树），我们可以先通过这两个序列重构出原始的二叉搜索树结构，然后再进行后序遍历。

以下是基本步骤：

1. **找到根节点**：在中序遍历中，根节点是唯一一个出现在左子部分和右子部分之间的元素。在先序遍历中，根节点总是第一个被访问的。

2. **确定左右子树**：先用中序遍历来找出根节点的位置，然后根据先序遍历的顺序，前一个元素就是左子树的终点，后一个元素就是右子树的起点。

3. **递归构建**：对左右子树分别应用相同的步骤，直到所有的子树都被处理完毕。

4. **后序遍历**：一旦所有子树的后序遍历都计算出来了，就可以按照“左 -> 右 -> 根”的顺序将它们组合起来形成后序遍历数组。

5. **存储后序遍历结果**：将后序遍历的节点依次放入数组中，记得从最后一个子树开始，因为后序遍历的顺序是最后访问的节点排在最前面。

下面是一个简单的示例代码片段：

#include <iostream>
using namespace std;

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

vector<int> postorderTraversal(TreeNode* root) {
    vector<int> res;
    if (!root) return res; // 空树直接返回

    // 找到根节点位置
    auto it = find(inOrder.begin(), inOrder.end(), root->val);
    assert(it != inOrder.end());

    // 递归获取左子树和右子树的后序
    res.insert(res.end(), postorderTraversal(root->left).begin(), postorderTraversal(root->left).end());
    res.insert(res.end(), postorderTraversal(root->right).begin(), postorderTraversal(root->right).end());
    res.push_back(root->val); // 把根节点添加到最后

    return res;
}

// 示例函数，假设你已经有了inOrder（中序遍历结果）数组
vector<int> getInOrder(TreeNode* root) { /* 获取并存储中序遍历 */ }

int main() {
    // 假设你已经得到了先序和中序遍历的结果
    vector<int> preorder = {1, 2, 4, 5, 3};
    vector<int> inorder = {4, 2, 5, 1, 3}; // 注意，这里inOrder需要实际生成

    // 构建二叉树
    TreeNode* root = buildTree(preorder);

    // 调用函数求后序
    vector<int> postorder = postorderTraversal(root);

    // 输出后序遍历结果
    for (const auto& num : postorder)
        cout << num << " ";
    cout << endl;

    return 0;
}