判断是否是BST的后序遍历序列
1.首先最后一个节点是根节点,根据BST的定义,从左到右查找第一个到大于跟节点的节点;
2.a.查找到那个节点后,首先判断它是不是就是根节点,如果是,说明右子树为空;接下去只需要递归验证左子树即可;
b.若那个节点就是begin节点,说明左子树为空,那么只需要判断右子树即可。
c.若有左右子树,继续验证剩下的节点是否每个都大于根节点,若不符合,直接返回false
3.满足2c条件,递归判断左,右子树是否满足。
public static boolean verify(int[] sequence, int begin, int end) {
if (sequence == null) {
return false;
}
if (begin <= end) {
return true;
}
int leftEnd = begin;
boolean flag = false;
//查找第一个大于根节点的节点
while (leftEnd < end && sequence[leftEnd] < sequence[end]) {
leftEnd++;
}
//节点不存在,即没有右子树,只需要继续判断左子树,递归判断
if (leftEnd == end) {
flag = verify(sequence, begin, leftEnd - 1);
}//若左子树不存在,只需要递归判断右子树
else if (leftEnd == begin) {
int tem = leftEnd;
while (tem < end) {
if (sequence[tem] <= sequence[end]) {
return false;
}
tem++;
}
flag = verify(sequence, leftEnd, end - 1);
} else {
//验证右子树是否满足每个节点都大于根节点
int tem = leftEnd;
while (tem < end) {
if (sequence[tem] <= sequence[end]) {
//不满足直接返回false
return false;
}
tem++;
}
//继续递归验证左子树
flag = verify(sequence, begin, leftEnd - 1);
//左子树满足,进入右子树递归,否则直接返回false
if (flag) {
//验证右子树
flag = verify(sequence, leftEnd, end - 1);
} else {
return false;
}
}
return flag;
}