255.Verify Preorder Sequence in Binary Search Tree

Kinda simulate the traversal, keeping a stack of nodes (just their values) of which we’re still in the left subtree. If the next number is smaller than the last stack value, then we’re still in the left subtree of all stack nodes, so just push the new one onto the stack. But before that, pop all smaller ancestor values, as we must now be in their right subtrees (or even further, in the right subtree of an ancestor). Also, use the popped values as a lower bound, since being in their right subtree means we must never come across a smaller number anymore.

https://leetcode.com/problems/verify-preorder-sequence-in-binary-search-tree/discuss/68142/

https://segmentfault.com/a/1190000003874375

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        Deque<Integer> path = new ArrayDeque<>();
        Integer low = Integer.MIN_VALUE;
        for(int i : preorder){
            if(i < low)
                return false;
            while(!path.isEmpty() && i > path.peek()){
                low = path.pop();
            }
            path.push(i);
        }
        return true;
    }
}

O1 space - Using Original array as stack

https://segmentfault.com/a/1190000003874375

public class Solution {
    public boolean verifyPreorder(int[] preorder) {
        // 用i标记栈顶
        int i = -1, min = Integer.MIN_VALUE;
        for(int num : preorder){
            if(num < min) return false;
            // 同样的解法，但是复用了数组作为栈，每pop一次相当于i--
            while(i >= 0 && num > preorder[i]){
                min = preorder[i--];
            }
            // push相当于i++
            preorder[++i] = num;
        }
        return true;
    }
}