输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历的结果。假设输入的数组的任意两个数字都互不相同。
例如,下图是后序遍历序列 1,3,2 所对应的二叉搜索树。
public class Solution {
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence == null || sequence.length == 0)
return false;
return verify(sequence, 0, sequence.length-1);
}
private boolean verify(int[] sequence, int first, int last) {
// 终止
if(last-first <= 1)
return true;
int curIndex = first;
int root = sequence[last];
// 树左
while(curIndex<last && sequence[curIndex]<=root)
curIndex++;
// 树右
for(int i=curIndex; i<last; i++) {
if(sequence[i]<root)
return false;
}
// 递归
return verify(sequence, first, curIndex-1) && verify(sequence, curIndex, last-1);
}
}