O(n) Recursive solution using unordered_map!


#1
TreeNode* Tree(vector<int> &A, vector<int> &B, int al,int ar,int bl,int br,unordered_map<int,int>&m){
     if(al>ar||bl>br)return NULL;
     TreeNode * root=new TreeNode(B[bl]);
     if(al==ar){
         return root;
     }
     root->left=Tree(A,B,al,m[B[bl]]-1,bl+1,bl+1+m[B[bl]]-1-al,m);
     root->right=Tree(A,B,m[B[bl]]+1,ar,bl+m[B[bl]]-al+1,br,m);
     return root;
}

TreeNode* Solution::buildTree(vector<int> &A, vector<int> &B) {
    unordered_map<int,int>m;
    for(int i=0;i<B.size();i++){
        m[B[i]]=i;
    }
    return  Tree(B,A,0, A.size()-1,0,B.size()-1,m);
}