class Solution {
    public boolean verifySequenceOfBST(int [] sequence) {
        // 迭代， 拿到最后一个元素 即根节点
        return dfs(sequence, 0 , sequence.length-1);
    }
    public boolean dfs(int [] sequence, int l, int r){
        if(l >= r){return true;}
        // 拿到最后一个元素
        int root = sequence[r];
        // 遍历前面比root小的数， 拿到一个k
        int k = l;
        while( k < r && sequence[k]<root) k++;
        // 拿到k后， 遍历判断后面的数是不是都符合条件
        for(int i = k; i< r; i++){
            if(sequence[i]<root){
                return false;
            }
        }
        // 注意这里是 r-1 (去掉root节点)
        return dfs(sequence, l , k-1 )&&dfs(sequence, k , r-1);

    }
}