Elegant recusive solution using only O(h) space memory


  • 0
    A
    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     struct TreeNode *left;
     *     struct TreeNode *right;
     * };
     */
     
     int search(int in[],int x,int low,int high){
         int i;
         for(i=low;i<=high;i++)
            if(in[i]==x)
                return i;
     }
     struct TreeNode * newnode(int x){
         struct TreeNode *p=NULL;
         p=(struct TreeNode *)malloc(sizeof(struct TreeNode));
         p->left=NULL;
         p->right=NULL;
         p->val=x;
         return p;
     }
     struct TreeNode * construct (int in[],int post[],int *index,int low,int high){
         if(low>high) return NULL;
         struct TreeNode *p=newnode(post[*index]);
         (*index)=(*index)-1;
         int k=search(in,p->val,low,high);
         if(low==high) return p;
         p->right=construct(in,post,index,k+1,high);
         p->left=construct(in,post,index,low,k-1);
         return p;
     }
    struct TreeNode * buildTree(int* inorder, int size, int* postorder, int psize) {
        if(!size) return NULL;
        int index=size-1;
        struct TreeNode *root=construct(inorder,postorder,&index,0,size-1);
        return root;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.