剑指offer——二叉搜索树的后序遍历序列

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

思路：首先二叉搜索树是指左子树全部小于根节点，右子树全部大于根节点的树。故：

对于一棵树：
首先找到右子树的第一个节点，然后判断右子树中是否有小于根节点的节点，若有，则输出false。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if (sequence.length == 0)//空树
            return false;
        if (sequence.length == 1)//单个节点树
            return true;
        return judge(sequence, 0, sequence.length-1);
    }
    public boolean judge(int[] a, int star, int end){
        if(star>=end){//迭代终止
            return true;
        }
        int i = star;
        while(a[i]<a[end]){//左子树
            i++;
        }
        for(int j = i;j<end;j++){//右子树
            if(a[j]<a[end])
                return false;
        }
        return(judge(a, star, i-1)&&judge(a, i,end-1));//对左子树和右子树进行判断
    }
}