//0034二叉搜索树的后序遍历序列
class Solution {
public:
    bool Dfs(int left, int right, vector<int>& sq)
    {
        if (left >= right) return true;

        int l = left;
        while(l < right && sq[right] > sq[l]) ++l;
        //这里的l是右子树的第一个节点

        int i = l;
        for (;i < right; ++i) {
            if (sq[i] < sq[right]) return false;
        }
        //树的合法性一般都是 左边 && 右边
        return Dfs(left, i - 1, sq) && Dfs(i, right - 1, sq);
    }

    bool verifySequenceOfBST(vector<int> sq) {
        return Dfs(0, sq.size() - 1, sq);          
    }
};