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

class Solution {
public:
    bool check(vector<int> s , int start,int end){
        if(start >= end){ //start与end重合
            return true;
        }
        int root = end; //根节点
        int j = end-1;
        while(j>=0 && s[j]>s[root]){
            j--;
        }
        for(int i = start;i<=j;i++){
            if(s[i]>s[root]){
                return false;
            }
        }
        return check(s,start,j) && check(s,j+1,end-1); //分别判断左子树和右子树
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        int size = sequence.size();
        if(size == 0){ //空树不是二叉搜索树
            return false;
        }
        return check(sequence,0,size-1);
    }
};