思路:倒序输出的时候是:根→右→左,其中左子节点的值恒小于根和右,于是便有遍历满足条件:①递增时候无任何问题,②递减时候要求必须小于以前所有数。依次为条件,先遍历入栈,再在递减时出栈对比即可。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0){
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        int len = sequence.length-1;
        for(int i=len; i>=0; i--){
            if(sequence[i]>root){
                return false;
            }
            while(!stack.isEmpty() && stack.peek()>sequence[i]){
                root = stack.pop();
            }
            stack.push(sequence[i]);
        }
        return true;
    }
}