题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回true，否则返回false。
思路：先在末尾找到根节点，从数组头部遍历，左子树默认应该都小于根节点，当遍历到某个数大于根节点，则为右子树。依次递归遍历。
解决方案：
public class Question33 {
public static boolean verifySequenceOfBST(int[] sequence){
if (sequence == null || sequence.length <= 0) return false;
return verifySequenceOfBST(sequence, 0, sequence.length - 1);
}
private static boolean verifySequenceOfBST(int[] sequence, int start, int end){
if (start >= end) return true;
int root = sequence[end];
int i = start;
while (sequence[i] < root){
i++;
}
int j = i;
while (j < end){
if (sequence[j] < root){
return false;
}
j++;
}
boolean left = verifySequenceOfBST(sequence, start, i - 1);
boolean right = verifySequenceOfBST(sequence, i, end - 1);
return left && right;
}
public static void main(String[] args) {
int[] sequence = new int[]{5,7,6,9,11,10,8};
System.out.println(verifySequenceOfBST(sequence));
}
}
