Relatively short C++ solution in O(N) and O(1) space


  • 0
    G
    class Solution {
    public:
    
        bool IsPreorder(vector<int>::iterator &Begin, vector<int>::iterator End, int Min, int Max)
        {
            if(Begin == End)
            {
                return (true);
            }
            
            if(*Begin >= Min && *Begin < Max)
            {
                int V = *Begin;
                Begin++;
                return (IsPreorder(Begin,End,Min,V) ||
                            IsPreorder(Begin,End,V,Max));
            }
            
            return (false);
        }
    
        bool verifyPreorder(vector<int>& preorder) 
        {
            auto B = preorder.begin();
            return IsPreorder(B,preorder.end(),INT_MIN,INT_MAX);
        }
    };

Log in to reply
 

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