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

class Solution {
public:
  bool VerifySquenceOfBST(vector<int> sequence) {
    return verify(sequence, 0, sequence.size() - 1);
  }

private:
  bool verify(vector<int>& seq, int l, int r) {
    if (l > r) return false;
    if (l == r) return true;

    int idx = distance(begin(seq), find_if(begin(seq) + l, begin(seq) + r,
            [&](int v) { return v > seq[r]; }));

    if (idx == r) return verify(seq, l, idx - 1);

    int k = idx + 1;
    while (k < r) {
      if (seq[k] <= seq[r]) return false;
      ++k;
    }
    if (idx == l) return verify(seq, idx, r - 1);

    return verify(seq, l, idx - 1) && verify(seq, idx, r - 1);
  }

};