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

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty())
            return false;

        return order(sequence, sequence.size());
    }

    bool order(const vector<int> &sequence, int length) {
        if (sequence.empty() || length <= 0)
            return false;
        
        int root = sequence[length - 1];
        
        int i = 0;
        for (; i < length - 1; i++) {
            if (sequence[i] > root) 
                break;
        }

        int j = i;
        for (; j < length - 1; j++) {
            if (sequence[j] < root)
                return false;
        }

        bool left = true;
        
        if (i > 0) {
            vector<int> tmp(sequence.begin(), sequence.begin() + i);
            left = order(tmp, i);
        }

        bool right = true;
        if (i < length - 1) {
            vector<int> tmp(sequence.begin() + i, sequence.end() - 1);
            right = order(tmp, length - i - 1);
        }

        return (left && right);
    }
};