class Solution {
    //46. 二叉搜索树的后序遍历序列
    public boolean verifySequenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) {
            return true;
        }
        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 cutIndex = first;

        //如果 当前节点在区间内，并且值小于根节点，就代表是左子树
        while(cutIndex < last && sequence[cutIndex] <= rootVal) {
            cutIndex++;
        }
        //cutIndex 代表 左子树的结尾
        for(int i = cutIndex +1; i <last; i++) {
            //右子树
            if (sequence[i] < rootVal) {
                return false;
            }
        }

        return verify(sequence, first, cutIndex - 1)
                && verify(sequence, cutIndex, last - 1);
    }
}