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

#include <climits>
#include <vector>
class Solution {
public:
    bool check(vector<int> sequence){
        if (sequence.size() <= 1)
            return true;
        int root = sequence[sequence.size() - 1];
        int index = sequence.size() - 1;

        for (int i = 0; i < sequence.size() - 1; i++){
            if (sequence[i] > root){
                index = i;
                break;
            }
                
        }

        vector<int> left(sequence.begin(), sequence.begin() + index);
        bool left_bool = check(left);
        vector<int> right(sequence.begin() + index, sequence.end() - 1);
        bool right_bool = check(right);
        
        if (right.size() >= 1){
            for (auto num : right){
                if (root > num)
                    return  false;
            }
        }
        return left_bool && right_bool;
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size() == 0)
            return false;
        bool result = check(sequence);
        return result;
    }
};