/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int>pos;


    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.empty())return NULL;
        int n=inorder.size();
        for(int i=0;i<n;i++){
            pos[inorder[i]]=i;
        }

        return build(0,n-1,0,n-1,preorder);
    }
    TreeNode* build(int il,int ir,int pl,int pr,vector<int>& preorder){
        TreeNode* ans=new TreeNode(preorder[pl]);  
        int root=preorder[pl];
        int k=pos[root];
        if(il<k)ans->left=build(il,k-1,pl+1,pl+k-il,preorder);
        if(ir>k)ans->right=build(k+1,ir,pl+k-il+1,pr,preorder);
        return ans;
    }
};