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

public:
    //int j=0,i=0,root=0;
    bool VerifySquenceOfBST(vector<int> sequence) {
        int size=sequence.size()-1;
        if(size==-1)return false;
        return  check(sequence,0,size);
    }
    bool check(vector<int> &sequence,int l,int r){
        if(l>=r)return true;
        //根结点是最后一个·
        int root=sequence[r];
        int j=r-1;
        //这里是找它的右子树，右子树的数都比根大
        while(j>=0&&sequence[j]>=root)j--;
        //判断左子树是否合法
        for(int i=l;i<=j;i++){
            if(sequence[i]>root)
                return false;//不合法直接false
        }
        //递归检查左右子树
        return check(sequence,l,j)&&check(sequence, j+1, r-1);///记得去掉根结点
    }
};