二叉搜索树的后序遍历序列【Java版】

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。（ps：我们约定空树不是二叉搜素树）

public class Solution {
    //1.拆分函数问题（如果递归时直接传入子数组，则开头出现同样的判断，但由于初次结果和后续不一样==>flag法没用，必须拆分）
    //2.递归拆分问题：由于原数组不需要修改，所以不用新占用空间来复制备份子数组，而是只要传入左右下标即可
    public boolean VerifySquenceOfBST(int [] sequence){
        if(sequence.length == 0)return false;
        return judge(sequence, 0, sequence.length-1);
    }
    boolean judge(int [] a, int left, int right){
        if(left>=right)return true;//分支结束两种情况:l==r单个叶；l>r为空  //这两个情况都是true
        int mid = 0;
        while(a[right]>a[mid])++mid;
        for(int i=mid+1;i<=right;++i){
            if(a[i]<a[right])return false;//发现问题直接false，否则继续往下挖
        }
        return judge(a,left,mid-1) && judge(a,mid,right-1);
    }
}
//复杂度分析：每个递归主体会减少一个节点，所以需要N次调用judge()函数；
//每次judge()函数：1) 时间上会遍历一轮数组  2) 空间上新定义几个固定变量(sequence一直没有去复制它，而是通过形参引用)
//所以总时间复杂度为 O(n^2)
//空间复杂度为 O(logn)==>递归栈空间