Simple solution along with explanation of approach


#1

//Approach-- Iteratively pick one node from preorder, and create a node(let’s call it x)
//Then search for x in Inorder.If position of x is “i” the left subtree== (start, i-1)
//and right subtree == (i+1,end)
//keep doing above steps recursively for each data in preorder

TreeNode* create(vector &pre, vector &ino, int start,int end,int &i){
// i == index of preorder

//Base Case
if(start>end) return NULL;
//Rec Case
TreeNode* cur= new TreeNode(pre[i]);//creating a new node
int index=-1;

for(int j=start;j<=end;j++){
    if(ino[j]==pre[i]){
        index=j;
        break;
    }
}
i++;
cur->left= create(pre,ino,start,index-1,i);
cur->right= create(pre,ino,index+1,end,i);
return cur;

}
TreeNode* Solution::buildTree(vector &pre, vector &ino) {
int n=pre.size();
int i=0;
TreeNode* root= create(pre,ino,0,n-1,i);
return root;
}