class Solution {
public:
    bool verifySequenceOfBST(vector<int> sequence) {
        //递归，找出中间节点，看看其左右是否满足左小于根 右大于根的特点，再递归左右子树

        return dfs(sequence,0,sequence.size() - 1);
    }

    bool dfs(vector<int> seq,int l,int r){
        if(l >= r) return true;

        int k = l;  
        int root = seq[r];
        while(k < r && seq[k] < root) k++;
        //cout << k << endl;


        for(int i = k;i < r;++i) 
            if(seq[i] < root) 
                return false;
        //cout << i << endl;   
       // return true;
        return dfs(seq,l,k-1) && dfs(seq,k,r - 1);  //是r-1不是r!
    }
};