【剑指offer】二叉搜索树的后续遍历序列

题目描述
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
1、思路分析
二叉搜索树的特点：左结点<根节点<右节点。后序遍历的定义是左右根，因此如果该整数数组是后序遍历的结果，最后一个元素一定是根节点，将前面的元素逐一与根节点比较，可以得到左右子树的分界点，此时能保证左子树的所有结点都是小于根节点的，还需判断右子树是否是都大于根节点，如果不是，返回false，如果是，则递归地判断左右子树是否是BST。
2、代码

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 0) return false;
        return IsTreeBST(sequence,0,sequence.length-1);
    }
    private boolean IsTreeBST(int[] sequence, int start, int end) {
        if(start >= end) return true;
        // 找左右子树的分界点
        int i = start;
        for(; i < end; i++) {
            if(sequence[i] > sequence[end]) break;
        }
        // 判断右子树是否都大于根节点
        for(int j = i; j < end; j++) {
            if(sequence[j] < sequence[end]) return false;
        }
        return IsTreeBST(sequence,0,i-1) && IsTreeBST(sequence,i,end-1);
    }
}