1. class Solution {
    2. public:
    3.     vector<int> seq; 
    4.     bool verifySequenceOfBST(vector<int> sequence) {
    5.         seq = sequence;
    6.         return dfs(0, seq.size() - 1);
    7.     }
    8.     bool dfs(int l, int r){
    9.         if (l >= r)  return true;
    10.         int root = seq[r];
    11.         int k = l;
    12.         while(k < r && seq[k] < root) k ++;
    13.         for(int i = k; i < r; i ++){
    14.             if(seq[i] < root) 
    15.                 return false;
    16.         }
    17.         return dfs(l, k - 1) && dfs(k, r - 1);
    18.         //k是右子树第一个，r-1是右子树最后一个（即右子树的跟、根）
    19.     }
    20. };