class Solution {
public:
    TreeNode* constructFromPrePost(const vector<int>&amp; preorder, const vector<int>& postorder) {
        if(preorder.empty() || postorder.empty()) return nullptr;
        for(int i = 0; i < postorder.size(); ++ i) {
            valToPostIndex[postorder[i]] = i;
        }
        return solve(preorder, postorder, 0, preorder.size() - 1, 0, postorder.size() - 1);
    }

private:
    unordered_map<int, int> valToPostIndex;     // val 在 postorder 中的下标

    TreeNode* solve(const vector<int>& preorder, const vector<int>& postorder, int l, int r, int ll, int rr) {
        if(l > r) return nullptr;
        if(l == r) {
            return new TreeNode(preorder[l]);
        }
        TreeNode *root = new TreeNode(preorder[l]);
        int lefSize = valToPostIndex[preorder[l + 1]] - ll + 1;       // 左子树大小可直接算出
        root -> left = solve(preorder, postorder, l + 1, l + lefSize, ll, ll + lefSize - 1);
        root -> right = solve(preorder, postorder, l + lefSize + 1, r, ll + lefSize, rr - 1);
        return root;
    }
};