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

#include <stack>
class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size() == 0) return false;
        return order(sequence, 0, sequence.size() - 1);
    }
    bool order(vector<int>& sequence, int l, int r) {
        // 剩一个节点的时候 返回 true
        if(l >= r) return true;
        int j;
        int mid = sequence[r];
         
        // 找到左子树和右子树的分界点，j代表左子树的最后一个索引位置
        for(j = l; j <r; j++) {
            int cur = sequence[j];
            if(cur > mid) break;
        }
         
        // 判断所谓的左子树中是否又不合法（不符合二叉搜索树）的元素
        for(int i = j; i < r; i++) {
            int cur = sequence[i];
            if(cur < mid) return false;
        }
        return order(sequence, l, j-1) && order(sequence, j, r-1);
    }
};

使用递归的思路，首先判断当前根节点下是否满足二叉搜索树（左子树的值都小于根节点，右子树的值都大于根节点），然后找到左右子树分界点，递归对左右子树进行判断是否满足二叉搜索树

注意：后续遍历末尾的值就是整棵树的根节点