《剑指offer》 第33题 二叉树的后序遍历序列

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

首先要知道后续遍历的特点。一个序列可以分为三个部分[a][b][c]，其中c是根节点，a整个序列是c的左子树，都比c小，b整个序列是c的右子树，都比c大。然后[a]序列又可以分成3个部分，其分法与刚开始相同。而左子树a和右子树b的分界线在于，遍历，直到找到一个数比根节点C大时，就找到了边界。
递归

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return judge(sequence, 0, sequence.length - 1);
    }

   public boolean judge(int [] sequence, int start, int end){
       if(start>=end)
            return true;//递归结束标志
       int mid = start;
       while(sequence[mid]<sequence[end]) //首先找到边界
           mid++;
       for(int i=mid;i<end;i++) {//左边确保都小于，不代表右边都小于，因此需要判断右边情况
            if(sequence[i]<sequence[end])
                return false;
        }
       return judge(sequence, start, mid-1) && judge(sequence, mid, end-1);//注意边界
   }   
}

ps:本来想尝试写写非递归，利用栈来写，然而我太菜了。