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

class Solution {
public:
    
    bool check(vector<int>& sequence,int l,int r)
    {
        if(l>r)
        {
            return true;
        }
        int root=sequence[r];
        int j=r;
        while(j>=0&&sequence[j]>=root)
        {
            j--;
        }
        for(int i=l;i<=j;i++)
        {
            if(sequence[i]>=root)
            {
                return false;
            }
        }
        return check(sequence,l,j)&&check(sequence,j+1,r-1);
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty())
        {
            return false;
        }
        return check(sequence,0,sequence.size()-1);
    }
};