LeetCode - Verify Preorder Sequence in Binary Search Tree

VerifyPreorderSequenceinBinarySearchTree.java

// Given an array of numbers, verify whether it is the correct preorder traversal sequence of a binary search tree.

// You may assume each number in the sequence is unique.

// Follow up:
// Could you do it using only constant space complexity?

// use stack
public boolean verifyPreorder(int[] preorder) {
    Stack<Integer> stack = new Stack<Integer>();
    int low = Integer.MIN_VALUE;
    for(int i = 0; i < preorder.length; i++){
        if(preorder[i] < low) return false;
        while(!stack.isEmpty() &&stack.peek() < preorder[i]){
            low = stack.pop();
        }
        stack.push(preorder[i]);
    }
    return true;
}

// O(1) space complexity
public boolean verifyPreorder(int[] preorder) {
    int low = Integer.MIN_VALUE, i = -1;
    for (int p : preorder) {
        if (p < low)
            return false;
        while (i >= 0 && p > preorder[i])
            low = preorder[i--];
        preorder[++i] = p;
    }
    return true;
}