cpp fast O(log(n)log(n)) Solution


  • 0
    R

    The idea is simple, binary search + divide & conquer

    bool isPreorder(vector<int>& preorder, int start, int end, int min, int max){
            if(start>=end)
                return true;
            if(preorder[start]>=max || preorder[start]<=min)
                return false;
            if(start==end-1)
                return true;
            int left=start,right=end,mid,rootval=preorder[start];
            while(left<right-1){
                mid=left+(right-left)/2;
                if (preorder[mid]>=max || preorder[mid]<=min)
                    return false;
                else if(preorder[mid]>rootval)
                    right=mid;
                else    
                    left=mid;
            }
            return isPreorder(preorder,start+1,right,min,rootval)&&isPreorder(preorder,right,end,rootval,max);
        }
    
        
    
        bool verifyPreorder(vector<int>& preorder) {
            return isPreorder(preorder,0,preorder.size(),INT_MIN,INT_MAX);
            
        }

Log in to reply
 

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