题解 | #二叉搜索树的后序遍历序列#

class Solution {
    bool check(vector<int>& sequence, int l, int r) {
        if(l >= r)
            return true;
        int root = sequence[r];
        int j = r - 1;
        while(j >= 0 && sequence[j] > root)
            j--;
        for(int i = l; i <= j; ++i) // 注意取等，考虑没有左子树的情况
            if(sequence[i] > root)
                return false;
        return check(sequence, l, j) && check(sequence, j + 1, r - 1);
    }
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        // 想要去判断某个序列是否是二叉搜索树的后序遍历
        // 后序 -> left right root
        // 二叉搜索树 -> right > root > left
        // 也就是问对于给定的序列，能否分成小 大 中这种形式
        int n = sequence.size();
        if(!n)
            return false;
        return check(sequence, 0, n - 1);
    }
};