//输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
class Solution {
public:
    vector<int> seq;
    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        return dfs(0,seq.size()-1);
    }
    bool dfs(int l,int r)
    {
        if(l>=r) return true;
        int root = seq[r];
        int k = l;
        while(k<r && seq[k]<root) k++;//左子树
        //遍历所有右子树的值是否大于根节点的值
        for(int i = k; i<r; i++)
            if(seq[i]<root)
                return false;
        return dfs(l,k-1) && dfs(k,r-1);
    }
};