34、二叉搜索树的前序遍历序列（33题的衍生题）

题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

import java.io.*;

class test  
{
    public static void main (String[] args) throws java.lang.Exception
    {
                // 测试用例
        //int[] sequence = new int[]{7,4,6,5};
        //int[] sequence = new int[]{};
        //int[] sequence = null;
        //int[] sequence = new int[]{15, 10, 8, 11, 18, 17, 19};
        //int[] sequence = new int[]{8,7,6,5};
        //int[] sequence = new int[]{8,9,10,11};
        //int[] sequence = new int[]{8};
        //int[] sequence = new int[]{8,7};
        //int[] sequence = new int[]{7,8};
        int[] sequence = new int[]{7,4,6,5,8,1};
        boolean result = VerifySquenceOfBST(sequence);
        System.out.println(result);
    }
    
    public static boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence==null || sequence.length==0) return false;
        if(sequence.length==1) return true;
        return verify(sequence, 0, sequence.length-1);
    }
    
    private static boolean verify(int[] sequence, int start, int end){
        if(start>=end) return true;
        int i=start+1;
        int rootVal = sequence[start];
        for(;i<=end;++i){
            if(sequence[i] > rootVal) break;
        }
        int j = i;
        for(;j<=end;++j){
            if(sequence[j]<= rootVal) return false;
        }
        return verify(sequence, start+1, i-1) && verify(sequence, i, end);
    }
}