输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
public class Solution {
public boolean VerifySquenceOfBST(int [] s) {
if(s.length==0) return false;
return verify(s,0,s.length-1);
}
public boolean verify(int []s,int l,int r){
if(l<r){
int rootVal = s[r];
int i=l;
for(;i<r;i++){
if(s[i]>rootVal) break;
}
int j=i;
for(;i<r;i++){
if(s[i]<rootVal) return false;
}
boolean left = verify(s,l,j-1);
boolean right = verify(s,j,r-1);
if(left&&right){
return true;
}else{
return false;
}
}
return true;
}
}
网友评论