二叉搜索树的后序遍历序列

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

来自牛客 剑指offer

题目描述

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

bool VerifySquenceOfBST(vector<int> sequence) {
    if (sequence.size() == 0) return false;
    return VerifySquenceOfBSTCore(sequence.begin(), sequence.end() - 1);
}
bool VerifySquenceOfBSTCore(vector<int>::iterator begin, vector<int>::iterator end) {
    if (end <= begin) return true;
    auto head = *end;
    auto lbegin = begin;
    auto lend = begin;
    while (lend < end - 1 && *lend++ < head)
        ;
    --lend;
    for (auto b = lend + 1; b < end - 1; ++b) {
        if (*b < head) return false;
    }
    auto rbegin = lend + 1;
    auto rend = end - 1;
    return VerifySquenceOfBSTCore(lbegin, lend) && VerifySquenceOfBSTCore(rbegin, rend);
}