二叉搜索树的后序遍历序列
1.
2.
import java.util.Arrays;
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence==null||sequence.length==0){
return false;
}
int root=sequence[sequence.length-1];
int i=0;
for(;i<sequence.length-1;i++){
if(sequence[i]>root){
break;
}
}
int j=i;
for(;j<sequence.length-1;j++){
if(sequence[j]<root){
return false;
}
}
boolean left=true,right=true;
if(i>0){
int leftSequence[] = Arrays.copyOfRange(sequence, 0, i);
left=VerifySquenceOfBST(leftSequence);
}
if(i<sequence.length-1){
int rightSequence[] = Arrays.copyOfRange(sequence, i, sequence.length-1);
right=VerifySquenceOfBST(rightSequence);
}
return left&&right;
}
}