题解 | #二叉搜索树的后序遍历序列#

我的想法比较直白简单，但是代码就相对复杂了：

1、对于二叉搜索树，主要的特性就是，节点的左边的所有节点一定比当前节点值小，节点右边的一定比当前的节点值大；
2、后序遍历出来的序列，主要特征就是该序列的最后一个值一定是改树的根节点。

根据以上两点就可以很好的判断出，整个序列哪一些是左子树，哪一些是右子树，因为比根节点小全都应该在左边，比根节点到的都应该在右边，如果违背了这个规则那么就说明不符合题目要求，返回false。

当判断了整改序列之后发现没有问题，那就还得分别判断左子树，和右子树。同样也可以当做一个完整的树来判断，这里就使用递归就OK了，直到最后，发现全部子序列都符合这个规则，那就说明这个序列符合要求，返回true。

 public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length == 1)return true;//如果一开始该序列就是只有一个数据，一定符合要求
        if(sequence.length == 0)return false;//同理一开始空序列，一定不符合要求
        Solution jz = new solution();
        int length = sequence.length;
        int root = sequence[length-1];//根节点
        ArrayList<Integer> left = new ArrayList<Integer>();
        ArrayList<Integer> right = new ArrayList<Integer>();

        boolean flag = false;//flag 的作用就是在循环判断序列时，当遇到了第一个比root大的值时变为true，也就是说从这里开始后面的序列都是右子树，这些值都要大于root，如果出现了不大于的情况就说明不符合要求。
        for (int i = 0 ; i < length ; i++){

            if(!flag && sequence[i] > root ){
                flag = true;
            }
            if(flag && sequence[i] < root ){
                return false;
            }

            if ( sequence[i] < root ){//保存左子树序列，由于不知道长度，使用list，递归前将他们转换回数组即可
                left.add(sequence[i]);
            }

            if ( sequence[i] > root && i < length-1){//保存右子树序列
                right.add(sequence[i]);
            }

        }
        int arrLeft[] = jz.change(left);//左子树List转换成数组
        int arrRight[] = jz.change(right);//同上

        boolean result = false;
        if (arrLeft == null || arrLeft.length < 2){//这里判断数组的长度之后在去递归，如果子序列的长度小于2 那么该子序列没必要去递归判断了，一定符合要求。-------（1）
            result = true;
        }else if ( VerifySquenceOfBST( arrLeft ) ){//递归判断左子序列
            result = true;
        }

        if(result && (arrRight == null || arrRight.length <2) ){//在左子树符合要求的前提先下再去判断右子树的长度，同上面（1）
            result = true;
        }else if ( result && !VerifySquenceOfBST( arrRight ) ){//递归判断右子序列
            result = false;
        }
        return  result;
    }

    public int[] change(ArrayList list){//将list转换成数组
        int length = list.size();
        int array[] = new int[length];
        for (int i = 0; i < length; i++){
            array[i] =(int)list.get(i);
        }
        return array;
    }