二叉搜索树的后序遍历序列-526互联

class Solution {
public:
    bool dfs(vector<int> q,int l,int r)
    {
        if(l>=r)    return true;
        int root=q[r];
        int idx=l;
        for (; idx < r; idx ++ )
            if(q[idx]>root) break;
        int t=idx;
        while(t<r)
        {
            if(q[t]<root)   return false;
            t++;
        }
        return dfs(q,l,idx-1)&&dfs(q,idx,r-1);
    }
    bool verifySequenceOfBST(vector<int> q) {
        //已知root的值，通过比较大小，判断出左右子树所在的区间,如果左右子树都是二叉搜索树，返回true
        if(!q.size())  return true;
        return dfs(q,0,q.size()-1);
    }
};