Output Limit Exceeded in array to Binary search tree


  • 2
    I

    Does anyone know why i keep receiving Output Limit Exceeded with this code?

    class Solution {
    public:
        void makeBST(TreeNode *&root, vector<int> &num, int left, int right){
            if(left > right){
                root = NULL;
                return ;
            }
            if(left == right){
                root = new TreeNode(num[left]);
                return;
            }
            int mid = left + (right-left)/2;
            root = new TreeNode(num[mid]);
            makeBST(root->left, num, left, mid);
            makeBST(root->right, num, mid+1, right);
        }
    
        TreeNode *sortedArrayToBST(vector<int> &num) {
            TreeNode *root;
            if(!num.size()) return NULL;
            makeBST(root, num, 0, num.size()-1);
            return root;
        }
    };

  • 0
    V

    Passing reference of root as a parameter can be avoided by declaring root inside "makeBST" function and returning root from that function


  • 0
    I

    but that's not an error, right? I've made the change and it's still OLE. Apparenty the error was here: makeBST(root->left, num, left, mid); it should be makeBST(root->left, num, left, mid-1);


  • 1
    X

    Recursive function calls may cost lots of time. Change your method to be non-recursive.


  • 3
    P

    I guess problem is in

      makeBST(root->left, num, left, mid);
    

    It should be,

      makeBST(root->left, num, left, mid-1);

  • 0
    L

    I have the same problem as yours,modify (left,mid) to (left,mid-1) would be OK

    class Solution {
    public:
        TreeNode *ArrayToBST(vector<int> &num,int low,int high)
        {
            if(num.size()==0) return NULL;
            TreeNode *root;
    
            if(low>high) return NULL;
            if(low==high)
            {
                root=new TreeNode(num[low]);
                return root;
            }
            int mid=(low+high)/2;
            root=new TreeNode(num[mid]);
            root->left=ArrayToBST(num,low,mid-1);
            root->right=ArrayToBST(num,mid+1,high);
            return root;
        }
    
        TreeNode *sortedArrayToBST(vector<int> &num) {
            return ArrayToBST(num,0,num.size()-1);
        }
    };

Log in to reply
 

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