# leetcode construct binary tree from preoder and inorder results

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    unordered_map<int, int> valToInorderIndex;
    for (int i = 0; i < inorder.size(); ++i) {
        valToInorderIndex[inorder[i]] = i;
    }
    return build(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1, valToInorderIndex);
}

TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir, unordered_map<int, int>& valToInorderIndex) {
    if (pl > pr) {
        return NULL;
    }
    
    TreeNode* root = new TreeNode(preorder[pl]);
    int rootInorderIndex = valToInorderIndex[root->val];
    int leftTreeSize = rootInorderIndex - il;
    
    root->left = build(preorder, inorder, pl + 1, pl + leftTreeSize, il, rootInorderIndex - 1, valToInorderIndex);
    root->right = build(preorder, inorder, pl + leftTreeSize + 1, pr, rootInorderIndex + 1, ir, valToInorderIndex);
    return root;
}