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

递归处理

即数组最后一个作为根结点，存在左边一段结点全部比根结点小，右边一段结点全部比根结点大，若不是，则返回false，

这里巧妙的是递归的设计。
以及如何在每一次遍历的过程中判断左边和右边这两子段符合规则。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence.length==0){
            return false;
        }

        return isbst(0,sequence.length-1,sequence);

    }
    public boolean isbst(int left,int right,int [] sequence){

        if(right<=left){
            //默认前面的正常搜索二叉树，
            //不能再进一步判断，返回true
            return true;
        }
        int lastright=right;//标记右边一段的下标
        int lastleft=left;//记左边一段的末下标
        int index=left;
        //遍历一次判断这次的数组是否符合
        while(index<right){
            if(sequence[index]<sequence[right]){
                //这里插入一个判断，只用一次遍历即可结束

                lastleft=index; //左边一段的末下标

                //用lastright和lastleft判断,
                //即在右边一段找到一个比根结点小的
                //因为右边一段的下标肯定比左边一段的大
                //左边一段遍历完了也即不可能再出现比根结点小的
                //如果出现，则返回失败
                if(lastleft>lastright){
                    return false;
                }
                index++;
            }
            if(sequence[index]>sequence[right]){
                //标记右边一段的下标
                lastright=index;
                index++;
            }
        }
        return  isbst(left,lastleft,sequence) &&
            isbst(lastleft+1,right-1,sequence);
    }
}