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