C++ O(n) Recursion


  • 0
    J

    Similar with 449 deserialize BST, recursively go through the number vector with upper and lower bound. Time Complexity O(n).

        bool verifyPreorder(vector<int>& preorder) {
            if(preorder.size()==0)return true;
            int pos=0;
            verify(preorder,INT_MIN,INT_MAX,pos);
            if(pos<preorder.size())return false;
            return true;
            
        }
        void verify(vector<int>&preorder, int low, int up, int& pos){
            if(preorder[pos]<low||preorder[pos]>up)return;
            int rootVal=preorder[pos];
            pos++;
            verify(preorder, low, rootVal, pos);
            verify(preorder, rootVal, up, pos);
        }
    

Log in to reply
 

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