Verify Preorder Array for Binary Search Tree

给一个int的array, 问你这个array是不是一个bst的preorder.

用stack做preorder遍历”

如果当前元素大于stack里的元素, 证明我们在遍历一个node的右节点, 这时,因为是preorder, 说明左节点已经遍历过了, 所以我们要把stack中所有小于当前元素的节点pop出来,并且用low记录最后的一个. 如果当前元素比low小, 证明循序有错误, 因为low是左子树中最小的元素.

然后每次把当前node放入stack, 最后stack中有元素也不影响判断是不是preorder

public boolean verifyPreorder(int[] preorder) {
        int low =  Integer.MIN_VALUE;
        Stack<Integer> st = new Stack<>();
        for(int p : preorder){
            if (p < low)
                return false;
            while (!st.empty()&& st.peek() < p)
                low = st.pop();
            st.push(p);
        }
        return true;
    }