剑指OfferJZ23：二叉搜索树的后序遍历序列-java版

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

二叉搜索树特点：对于某个节点，它的左子树都小于当前节点，它的右子树都大于当前节点 后序遍历特点：左右中（后序遍历的末尾数字是二叉树的root节点）

如下列一个数组： 首先根据后序遍历特点，可以得到数组的末尾数字是二叉树的root节点，如图可以得到二叉树的根节点为4 然后根据二叉搜索树特点，可以划分出root节点的左右子树，小于root节点的数为左子树，大于root节点的树为右子树，如图小于4的数1,2,3为节点4的左子树，大于4的数5为节点4的右子树 以此类推。。。 在剩下的数组1,3,2中，末尾数2为root节点，小于2的数1为节点2的左子树，大于2的数3为节点2的右子树

注意特殊情况： 情况1.如果小于末尾数字的数字组成的序列不连续，或大于末尾数字的数字组成的序列不连续（则不满足后序序列的遍历特点） 如图：在数组 4 ，1,3,2中，小于末尾数2的数为1；大于末尾数的数字为3,4，由于3,4之间隔了一个数字，不连续，所以不满足后序遍历条件

情况2：如果满足情况1：小于和大于末尾数字的数字各自组成的序列都是连续的，但如果大于末尾数的序列在小于末尾数的序列前面（则不满足二叉搜索树的特点） 如图：大于5的连续序列3,4在小于5的连续序列1,2前面，就不行

 public class jz23 {
    private boolean solve(ArrayList list){
        //递归终止的条件
        if (list.size() == 0 || list.size() == 1) {
            return true;
        }
        ArrayList minList = new ArrayList();//比当前节点小的数（作为左子树）
        ArrayList maxList = new ArrayList();//比当前节点大的数（作为右子树）
        int endNumber=list.get(list.size()-1);//末尾数字
        int minIndex=-1;//记录minList中第一个数字的位置
        int maxIndex=-1;//记录maxList中第一个数字的位置
        for(int i=0;iendNumber){//大于末尾数字的数
                if(maxIndex==-1){
                    maxIndex=i;
                }
                maxList.add(list.get(i));
            }else if(list.get(i)maxIndex){//情况2：大于末尾数的序列在小于末尾数的序列的前面，不满足后序遍历性质
                return false;
            }
            for(int i=maxIndex;i