255. Verify Preorder Sequence in Binary Search Tree

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?

Solution1：

          4(min)
    2           *6
1     3      5    7
[4 2 1 3 6 5 7]

思路： 模拟树遍历的过程。遍历输入数组，对当前元素elem，它的上限是没有问题的，可以就当作树中右侧新的branch。但需要check它的下限，不能小于它parent结点的值min_th。min_th通过stack维持。

Time Complexity: O(N) Space Complexity: O(N)

Solution2：在输入数组前部自身 当作stack：维持指针i

思路： 不会影响正常的遍历
Time Complexity: O(N) Space Complexity: O(1)

Solution1 Code：

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int min_th = Integer.MIN_VALUE;
        Deque<Integer> stack = new ArrayDeque();

        for (int elem : preorder) {
            if (elem < min_th) return false;
            while (!stack.isEmpty() && elem > stack.peek()) // right branch
                min_th = stack.pop();

            stack.push(elem);
        }
        return true;
    }
}

Solution2 Code：

class Solution {
    public boolean verifyPreorder(int[] preorder) {
        int min_th = Integer.MIN_VALUE, i = -1;
        
        for (int elem : preorder) {
            if (elem < min_th) return false;
            while (i >= 0 && elem > preorder[i])
                min_th = preorder[i--];
            
            preorder[++i] = elem;
        }
        return true;
    }
}