Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.4 kB
0
Indexable
/************************************************************

    Following is the TreeNode class structure

    template <typename T>
    class TreeNode {
       public:
        T data;
        TreeNode<T> *left;
        TreeNode<T> *right;

        TreeNode(T data) {
            this->data = data;
            left = NULL;
            right = NULL;
        }
    };

************************************************************/

//          preorder index  

int findpos(vector<int>&inorder,int element,int n){
    for(int i=0;i<n;i++){
        if(inorder[i]==element) return i;
    }
    return -1;
}            

TreeNode<int>* solve(int &i,vector<int> &inorder,vector<int> &preorder, int s,int e,   int n){
    
    if(i>=n || s>e) return NULL;

    int element =preorder[i++];
    TreeNode<int>* node=new TreeNode<int>(element);

    int pos=findpos(inorder,element,n);

    node->left = solve(i,inorder,preorder,s,pos-1,n);
    node->right = solve(i,inorder,preorder,pos+1,e,n);
    return node;

}
TreeNode<int> *buildBinaryTree(vector<int> &inorder, vector<int> &preorder)
{
	//    Write your code here  //INORDER LNR....... PREORDER NLR
    int n=inorder.size();
    int pin=0;
    TreeNode<int> *ans =solve(pin,inorder,preorder,0,n-1,n); //starting and ending index of inorder
    return ans;

}