剑指offer15 JZ33 二叉搜索树的后序遍历序列

首先是二叉搜索树（左子树每个节点的值 < 该节点的值 < 右子树每个节点的值）的特点；
其次是后序遍历（对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身）的特点。

第一步：找到数组最后一位，即根节点root。紧接着
第二步：获取整个数组的长度，开始遍历并与root值比较，第一个大于root的值就是左右子树的分界点。
第三步：遍历右子树，验证是否符合二叉搜索树的概念；如上图，以12为分界点的右边所有节点都是大于root的，所以是符合二叉搜索树的。
第四步：继续往下递归，查看余下的左右子树是否符合。这里再放一个不符合的数组案例给大家对比一下，数字图标表示步骤：

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int size=sequence.length;
        if(size==0){
            return false; //空节点不是搜索数
        }
        return check(sequence,0,size-1);
    }
    public boolean check(int [] sequence,int left ,int right){
        if(left>=right){
            return true; //只有一个节点 程序出口
        }
        int root=sequence[right];//找到根节点
        //划分出右子树 从根节点的左边第一个节点开始
        int r=right-1;
        //第一个大于根节点的的数就是左右子树的分界点
        while(r>=0&& sequence[r]>root){
            r--;
        }
        //检查左子树是否合法，左子树所有节点要小于根节点
        for(int i=left;i<=r;i++){
            if(sequence[i]>root){
                return false;
            }
        }
        //递归检查左子树右子树
        return check(sequence,left,r) && check(sequence,r+1,right-1);
     
        
    }
}