题解 | #二叉搜索树的后序遍历序列#

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

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;
    }
}