【剑指offer】面试题33：二叉搜索树的后序遍历序列

public class  {
    public boolean VerifySquenceOfBST(int[] sequence) {
        
        if (sequence == null || sequence.length == 0)
            return false;

        return verify(sequence, 0, sequence.length);
    }

    private boolean verify(int[] s, int lo, int hi) {
        // 退出边界
        if (hi - lo <= 1)
            return true;

        // 查找划分下标
        int split = lo;
        for (; split < hi - 1; split++) {
            if (s[split] > s[hi - 1]) {
                break;
            }
        }

        // 验证右边部分大于等于最后的节点
        for (int i = split; i < hi - 1; i++) {
            if (s[i] < s[hi - 1]) {
                return false;
            }
        }

        return verify(s, lo, split) && verify(s, split, hi - 1);
    }
}