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

class Solution {
  public:
    bool verify(vector<int>& sequence, int l, int r) {
        if (l >= r) return true; // base case
        int root = sequence[r];
        int lr=l; // left boundary of the right subtree
        for (; lr<r; lr++) {
            if (sequence[lr] > root) break;
        }
        for (int i=lr; i<r; i++){
            if (sequence[i] < root) return false;
        }
        return verify(sequence, l,lr-1) && verify(sequence, lr, r - 1);
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if (sequence.size() == 0) return false;
        return verify(sequence, 0, sequence.size() - 1);
    }
};

Segfault => index不对