struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(-1), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    TreeNode* traverse(vector<int>& inorder, vector<int>& postorder, int inorderBegin, int inorderEnd, int postorderBegin, int postorderEnd) {
        if(postorderBegin == postorderEnd) return nullptr;

        TreeNode* root = new TreeNode(postorder[postorderEnd-1]);

        if(postorderEnd - postorderBegin == 1) return root;

        int delimeter = 0;
        for(delimeter = inorderBegin; delimeter < inorderEnd; delimeter++) {
            if(inorder[delimeter] == root->val)
                break;
        }

        root->left = traverse(inorder, postorder, inorderBegin, delimeter, postorderBegin, postorderBegin + (delimeter - inorderBegin));
        root->right = traverse(inorder, postorder, delimeter + 1, inorderEnd, postorderBegin + (delimeter - inorderBegin), postorderEnd-1);

        return root;
    }

    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if(inorder.size() == 0 || postorder.size() == 0) return nullptr;
        return traverse(inorder, postorder, 0, inorder.size(), 0 , postorder.size());
    }
};