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

二叉树的前序遍历顺序为：根节点、左子树、右子树；中序遍历顺序为：左子树、根节点、右子树。因此，如果已知一个二叉树的前序遍历和中序遍历，就可以推导出该二叉树的后序遍历。

具体实现方法如下：

1. 定义二叉树节点结构体

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

2. 以前序遍历的第一个节点作为根节点，在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树两部分。

3. 递归构建左子树和右子树，左子树的前序遍历和中序遍历可以分别由原先的前序遍历和左子树部分的中序遍历得到，右子树的前序遍历和中序遍历可以分别由原先的前序遍历和右子树部分的中序遍历得到。

4. 后序遍历的顺序为左子树、右子树、根节点，因此在递归构建完左子树和右子树之后，将当前节点的值加入到结果数组中即可。

完整代码如下：

class Solution {
public:
    vector<int> inorder, preorder, postorder;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        this->inorder = inorder;
        return build(0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    TreeNode* build(int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) return NULL;

        int rootVal = preorder[preLeft];
        int index = 0;
        for (int i = inLeft; i <= inRight; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }

        int leftSize = index - inLeft;
        TreeNode* root = new TreeNode(rootVal);
        root->left = build(preLeft + 1, preLeft + leftSize, inLeft, index - 1);
        root->right = build(preLeft + leftSize + 1, preRight, index + 1, inRight);

        postorder.push_back(rootVal);

        return root;
    }
};