class Solution {
public:
    vector<int> seq;

    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        if (seq.empty()) return true;
        return dfs(0, seq.size() - 1);
    }

    bool dfs(int l, int r) {
        if (l >= r) return true;//当前序列长度为0，肯定合法，返回true
        int root = seq[r];//根节点就是当前序列的最后一个元素
        int k = l;
        //算出左子树的终点在什么位置
        while (k < r && seq[k] < root) k++;//此时k就是右子树的第一个元素
        //判断右子树是否合法
        for (int i = k; i < r; i++) {
            if (seq[i] < root)
                return false;//有右子树元素小于根节点则不合法，返回false
        }
        return dfs(l, k - 1) && dfs(k, r - 1);//递归左右两边
    }
};