【剑指Offer】33. 二叉搜索树的后序遍历序列

public class Solution {
    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 curIndex = first;
        int root = sequence[last];
        
        // 树左
        while(curIndex<last && sequence[curIndex]<=root) 
            curIndex++;
        
        // 树右
        for(int i=curIndex; i<last; i++) {
            if(sequence[i]<root)
                return false;
        }
        
        // 递归
        return verify(sequence, first, curIndex-1) && verify(sequence, curIndex, last-1);
    }
}