struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), 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>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir) {
        if(pl == pr) return nullptr;

        TreeNode* root = new TreeNode(preorder[pl]);

        if(pr - pl == 1) return root;

        int delimeter = 0;

        for(delimeter = il; delimeter < ir; delimeter++) {
            if(inorder[delimeter] == preorder[pl]) {
                break;
            }
        }

        root->left = traverse(preorder, inorder, pl+1, pl+1+delimeter-il, il, delimeter);
        root->right = traverse(preorder, inorder, pl+1+delimeter-il, pr, delimeter+1, ir);
        
        return root;
    }

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