Recursive Solution, Time complexity O(n)


  • 0
    A
    bool verifyPreorder(vector<int>& preorder, int &start, int min, int max) {
      if(start >= preorder.size()) return true;
      if(preorder[start] < min || preorder[start] > max) {
        return false;
      }
      start++;
      /* equal elements are on LHS */
      return verifyPreorder(preorder, start, min, preorder[start-1]) || verifyPreorder(preorder, start, preorder[start-1] + 1, max);
    }
    
    bool verifyPreorder(vector<int>& preorder) {
      int start = 0;
      return verifyPreorder(preorder, start, INT_MIN, INT_MAX);
    }
    

Log in to reply
 

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