Problem

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?

思路（divide & conquer）

• 由于要验证一个范围内的数组是否为valid bst。 所以函数需要起始位置s以及终止位置e
• 选取起始位置作为pivot， 从s + 1 开始到 e，
  • 找到第一个比pivot大的数的位置 bigger， 也就是当前节点的右子树第一个节点
  • 如果已经存在比pivot大的数， 该数的后面竟然后有比pivot小的， 那么这个肯定不是bst
• 如果这个bigger存在（也就是说当前节点有右子树）， 那么继续检验这个右子树， 以及当前节点的左子树

    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return true;
        }
        return verifyBst(preorder, 0, preorder.length - 1);
    }

    private boolean verifyBst (int[] nums, int start, int end) {
        if (start >= end) return true;

        int root = nums[start];
        int right = -1;
        for (int i = start + 1; i <= end; i++) {
            if (right == -1 && nums[i] > root) {
                right = i;
            } 
            if (right != -1 && nums[i] < root) {
                return false;
            }
        }
        if (right == -1) {
            return verifyBst(nums, start + 1, end);
        } 
        return verifyBst(nums, start + 1, right - 1) && verifyBst(nums, right, end);
    }
}

思路（stack）

    public boolean verifyPreorder(int[] preorder) {
        if (preorder == null || preorder.length == 0) {
            return true;
        }
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MIN_VALUE;

        for (int i = 0; i < preorder.length; i++) {
            if (root > preorder[i]) return false;

            // 栈维护的是比preorder【i】 大的元素， 也就是保存root， 以及它的左子树。 
            // 当遇到比栈顶大的数， 意味着栈顶便是preorder【i】的 根节点， 否则依然还是栈顶的左子树
            while (!stack.isEmpty() && preorder[i] > stack.peek()) {
                root = stack.pop();
            }
            stack.push(preorder[i]);
        }
        return true;
    }