题目描述

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

样例

输入：[4, 8, 6, 12, 16, 14, 10]

输出：true

算法1

后续遍历，最后一个元素既是根节点，然后根据根节点把树分为左右子树，左子树全部小于根节点
右子树全部大于根节点，因此当我们找到根节点值的时候，遍历数组，找到第一个大于根节点的元素下标
作为分割线，前面是左子树，后面是右子树，左子树不会有大于根节点的，判断右子树是否满足条件
不满足就返回false，满足就不断地向下递归。

具体详情看下述代码。 先序遍历也可以这样做。

keys：当需要我们处理遍历顺序的时候，我们先找到根节点，然后递归处理左右子树。

参考文献

剑指offer

C++ 代码

bool isNice(const vector<int> &sequence,int begin,int end)
{
    if(begin >= end)
        return true;
    int elem = sequence[end];
    int index = begin;
    for(index = begin; index < end; ++index)
    {
        if(sequence[index] > elem)
            break;
    }
    for(int i = index; i < end; ++i)
    {
        if(sequence[i] < elem)
            return false;
    }
    return isNice(sequence,begin,index-1) && isNice(sequence,index,end-1);
}
bool verifySequenceOfBST(vector<int> sequence) {
    if(sequence.empty())
        return true;
    return isNice(sequence,0,sequence.size()-1);
}