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

1.递归检查

2.假设遍历找到的第一个大于根的为属于右子树，将左右子树分界，分别递归检查

3.分界点pos默认为区间右限，找不到则不需要赋值

4.边界为左右界限不存在，即检查到了叶子节点

#include <utility>
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty()) return false;
        return check(sequence, 0, sequence.size() - 1);
    }
    bool check(vector<int> seq, int l, int r) {
        //边界
        if(l > r) return true;
        
        int i;
        int pos = r;
        for(i = l; i < r; i++) {
            if(seq[i] > seq[r]) {
                pos = i;
                break;
            }
        }
        for(; i < r; i++) {
            if(seq[i] < seq[r]) return false; 
        }
        return check(seq, l, pos - 1) & check(seq, pos, r - 1);
    }
};