解题思路在于:
这是一颗二叉搜索树,特性是左子树的值小于根节点,右子树的值大于根节点
遍历查找是否满足这个性质
已知这是后序遍历:左右根
得出数组中最后一位是根节点
比他小的是左子树,大是右子树,如果每次都能遍历当前数组,满足条件
public boolean verifySequenceOfBST(int [] sequence) {
if(sequence == null) return false;
if(sequence.length == 0) return true;
int root = sequence[sequence.length - 1];
int i = 0;
for(;i < sequence.length - 1;i++){
if(sequence[i] > root){
break;
}
}
int[] lt = new int[i];
for(int j = 0;j < i;j++){
lt[j] = sequence[j];
}
int j = i;
for(;j < sequence.length - 1;j++){
if(sequence[j] < root){
return false;
}
}
int[] gt= new int[j - i];
for(int k = 0 ; k < j - i;k++){
gt[k] = sequence[i + k];
}
boolean lb = true;
if(i > 0)
lb = verifySequenceOfBST(lt);
boolean gb = true;
if(j > 0)
gb = verifySequenceOfBST(gt);
return lb&&gb;
// return true;
}