二叉树已知前序中序求后序代码详解

二叉树的前序遍历和中序遍历可以确定一棵二叉树，因此可以通过已知的前序遍历和中序遍历来构建出一棵二叉树。而求解二叉树的后序遍历则需要使用递归来实现。

具体的算法流程如下：

1. 如果前序遍历序列和中序遍历序列为空，则返回空节点；
2. 取前序遍历序列的第一个元素作为根节点；
3. 在中序遍历序列中找到根节点，确定左子树和右子树的中序遍历序列；
4. 根据左子树的中序遍历序列和前序遍历序列递归构建左子树；
5. 根据右子树的中序遍历序列和前序遍历序列递归构建右子树；
6. 将根节点加入后序遍历序列中；
7. 返回根节点。

下面是代码实现：

#include <iostream>
#include <vector>

using namespace std;

// 二叉树节点结构体
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 根据前序遍历序列和中序遍历序列构建二叉树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.empty() || inorder.empty()) {
        return nullptr;
    }
    // 取前序遍历序列的第一个元素作为根节点
    int root_val = preorder[0];
    TreeNode* root = new TreeNode(root_val);
    // 在中序遍历序列中找到根节点，确定左子树和右子树的中序遍历序列
    int root_idx = 0;
    for (int i = 0; i < inorder.size(); i++) {
        if (inorder[i] == root_val) {
            root_idx = i;
            break;
        }
    }
    vector<int> left_inorder(inorder.begin(), inorder.begin() + root_idx);
    vector<int> right_inorder(inorder.begin() + root_idx + 1, inorder.end());
    // 根据左子树的中序遍历序列和前序遍历序列递归构建左子树
    vector<int> left_preorder(preorder.begin() + 1, preorder.begin() + 1 + left_inorder.size());
    root->left = buildTree(left_preorder, left_inorder);
    // 根据右子树的中序遍历序列和前序遍历序列递归构建右子树
    vector<int> right_preorder(preorder.begin() + 1 + left_inorder.size(), preorder.end());
    root->right = buildTree(right_preorder, right_inorder);
    return root;
}

// 后序遍历二叉树
void postorder(TreeNode* root, vector<int>& ans) {
    if (root != nullptr) {
        postorder(root->left, ans);
        postorder(root->right, ans);
        ans.push_back(root->val);
    }
}

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

输出结果为：

4 5 2 6 3 1

这就是二叉树的后序遍历序列。