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

基本思路：

1. 后序遍历的顺序是左右中，所以能确定的是数组最后一个数一定是根节点的值
2. 二叉搜索树的性质是左子树的值都小于根节点的值，而右子树的值都大于根节点的值
3. 可以根据这个性质尝试将数组划分为三块，从左到右分别是小于根节点的部分（左子树）、大于根节点的部分（左子树）、根节点，如果划分失败则直接返回false
4. 子数组可以递归求解，结束条件是数组中只有一个或更少的元素
5. sequence为空时需要返回false，需要特殊判断

class Solution {
public:
    bool VerifySquenceOfBST2(vector<int> sequence, int l, int r) {
        if (l >= r) return true;
        int rtv = sequence[r], bigger = r;
        bool islower = true;
        for (int i = l; i < r; i++) {
            if (sequence[i] == rtv) return false;
            else if (sequence[i] > rtv) {
                if (islower) {
                    islower = false;
                    bigger = i;
                }
            }
            else {
                if (!islower) return false;
            }
        }
        return VerifySquenceOfBST2(sequence, l, bigger - 1) && VerifySquenceOfBST2(sequence, bigger, r - 1);
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.empty()) return false;
        return VerifySquenceOfBST2(sequence, 0, sequence.size() - 1);
    }
};