题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0){
return false;
}
return VerifySquenceOfBST(sequence, 0, sequence.length-1);
}
public boolean VerifySquenceOfBST(int [] sequence, int start, int end) {
if(start==end){
return true;
}
//后序遍历，最后一个元素是根
int root = sequence[end];
//左子树都小于root
int i=start;
while(sequence[i]<root&&i<end){
i++;
}
//没有右子树
if(i==end){
return VerifySquenceOfBST(sequence,start,i-1);
}
//右子树都大于root，如果不满足，则返回false
for(int j=i; j<end; j++){
if(sequence[j]<root){
return false;
}
}
//没有左子树
if(i==start){
return VerifySquenceOfBST(sequence,i,end-1);
}
//递归检查左、右子树
return VerifySquenceOfBST(sequence,start,i-1)
&& VerifySquenceOfBST(sequence,i,end);
}
}
