public:
//int j=0,i=0,root=0;
bool VerifySquenceOfBST(vector<int> sequence) {
int size=sequence.size()-1;
if(size==-1)return false;
return check(sequence,0,size);
}
bool check(vector<int> &sequence,int l,int r){
if(l>=r)return true;
//根结点是最后一个·
int root=sequence[r];
int j=r-1;
//这里是找它的右子树,右子树的数都比根大
while(j>=0&&sequence[j]>=root)j--;
//判断左子树是否合法
for(int i=l;i<=j;i++){
if(sequence[i]>root)
return false;//不合法直接false
}
//递归检查左右子树
return check(sequence,l,j)&&check(sequence, j+1, r-1);///记得去掉根结点
}
};