I don't know why i am getting runtime error for large input .Can someone help me?


  • 0
    G
    class Solution {
    public:
        int search(vector<int> &inorder,int low,int high,int target)
        {
            int i=0;
            for(i=low;i<=high;i++)
            {
                if(inorder[i]==target)
                    return i;
            }
        }
         TreeNode* prein(vector<int> &postorder,vector<int> &inorder,int ilow,int ihigh,int *postindex)
        {
            if(ilow>ihigh)
                return NULL;
            TreeNode *root=new TreeNode(postorder[*postindex-1]);
            (*postindex)--;
            if(ilow==ihigh)
                return root;
            int inindex=search(inorder,ilow,ihigh,root->val);
            root->left=prein(postorder,inorder,ilow,inindex-1,postindex);
            root->right=prein(postorder,inorder,inindex+1,ihigh,postindex);
            return root;
        }
        TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder) {
            int p1=postorder.size();
            int i1=inorder.size();
            if(p1==0 && i1==0)
                return NULL;
            return prein(postorder,inorder,0,i1-1,&p1);
            
            
        }
    };

  • 0
    F

    First you may need to exclude 'postindex' as part of the passing arguments. You could declare it as global variable. Second, you need to change the order in which you call prein() function for left and right child. To reverse the process and reconstruct the tree, call root->right=prein(..) first, then root->left.


  • 0
    G

    you can't make any global variables in oj because all the test cases are tested in 1 pass so for every test case variables need to be initialized ,changing the order of call for right sub tree first and then left sub tree.


  • 0
    F

    Just use little bit of creativity. Declare variable postindex global to the Solution class and initialize it under the buildTree() function. I tested such approach and worked like a charm. below is the code.


  • 0
    F
    class Solution
    {
     int postIndex; //global to class
     int search(vector<int> &a, int start, int end, int target)
     {
    	 for (int i=start; i<=end; i++)
    		 if (a[i]==target)
    			 return i;
     }
    TreeNode *reconstructTree(vector<int> &in, vector<int> &post, int start, int end)
    {
      if(start > end) return NULL;
      TreeNode *node = new TreeNode(post[postIndex--]);
      if(start == end) return node;
      int inIndex = search(in, start, end, node->val);
      node->right = reconstructTree(in, post, inIndex+1, end);
      node->left = reconstructTree(in, post, start, inIndex -1);
      return node;
    }
    public:
        TreeNode *buildTree(vector<int> &inorder, vector<int> &postorder)
        {
            if (inorder.size()<1) return NULL;
            postIndex=inorder.size()-1; //initialize post index here
            return reconstructTree(inorder, postorder, 0, inorder.size()-1);
        }
    };

  • 0
    I

    you can make this linear by using a hash map instead of that loop.


  • 0
    S

    can u plz tell why runtime error has been removed by changing the order of function calls?
    yes u r right..changing the order of function calls works for me too but i am not able to understand the reason behind this.


Log in to reply
 

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