12lines C++ beats 93.97% O(1) space - simple recursive helper function


  • 0
    S

    Basic idea:
    To use min & max to see if the number can fit in current tree position
    if it can NOT -> directly return
    else -> increment iterator and recursively call to left and right subtree

    If at the end we still have numbers remain, return false.

    void helper(vector<int>& nums,int& i, int low, int high){
            if(i>=nums.size() || nums[i]>high || nums[i]<low) return;
            int cur=nums[i++];
            helper(nums,i,low,cur);
            helper(nums,i,cur,high);
            return;
        }
        bool verifyPreorder(vector<int>& preorder) {
            int i=0;
            helper(preorder,i,INT_MIN,INT_MAX);
            return i>=preorder.size() ? true : false;
        }
    

Log in to reply
 

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