题解 | #从中序与后序遍历序列构造二叉树#

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

private:
    TreeNode* helper(std::vector<int>& inorder, int inStart, int inEnd, std::vector<int>& postorder, int postStart, int postEnd) {
        if (inStart > inEnd || postStart > postEnd)
            return nullptr;

        int rootVal = postorder[postEnd];
        int rootIndex = 0;
        for (int i = inStart; i <= inEnd; ++i) {
            if (inorder[i] == rootVal) {
                rootIndex = i;
                break;
            }
        }

        TreeNode* root = new TreeNode(rootVal);
        int leftSize = rootIndex - inStart;

        root->left = helper(inorder, inStart, rootIndex - 1, postorder, postStart, postStart + leftSize - 1);
        root->right = helper(inorder, rootIndex + 1, inEnd, postorder, postStart + leftSize, postEnd - 1);

        return root;
    }
};

buildTree函数接受两个vector参数：inorder表示二叉树的中序遍历序列，postorder表示二叉树的后序遍历序列。函数通过递归实现了根据中序遍历和后序遍历构建二叉树的过程。

在函数内部，首先通过判断inStart大于inEnd或者postStart大于postEnd来定义递归的终止条件，即遍历完毕。然后取出postorder序列的最后一个元素作为当前子树的根节点值rootVal。接着，在inorder序列中找到rootVal的索引位置rootIndex，以此将中序遍历序列分成左子树和右子树。

然后创建一个新的TreeNode对象root，将rootVal赋值给root的val成员。计算左子树的大小leftSize，即rootIndex减去inStart。接着，递归构建左子树，左子树的中序遍历序列是从inStart到rootIndex-1，后序遍历序列是从postStart到postStart+leftSize-1。递归构建右子树，右子树的中序遍历序列是从rootIndex+1到inEnd，后序遍历序列是从postStart+leftSize到postEnd-1。将左右子树链接到root的left和right成员。

最后，返回根节点root。

ps:中序遍历的顺序为左根右，后序遍历的顺序为左右根，先序遍历为根左右