JZ23-二叉搜索树的后序遍历序列

class Solution2 {
    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 rootVal = sequence[last];
        int i = first;
        while (i < last && sequence[i] <= rootVal) {
            i++;
        }
        for (int j = i; j < last; j++) {//右子树中有小于根节点的话，就false
            if (sequence[j] < rootVal)
                return false;
        }
        return verify(sequence, first, i - 1) && verify(sequence, i, last - 1);//递归判断左右子树
    }
}