【六分钟学算法-剑指offer系列（第一季完结篇）】34.二叉搜索树的后序遍历序列

这是【六分钟学算法】的第一季，剑指offer系列，作者利用了三十天时间C++实现，带你玩转算法，剑指offer，喜欢的话可以点赞关注＋收藏，本篇第一季完结篇。

---

题目34. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。

如果是则返回true，否则返回false。

假设输入的数组的任意两个数字都互不相同。

数据范围
数组长度 [0,1000]。

样例

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

输出：true

【题解】-- 后序遍历

1. 本题的核心思想是：在BST中，根结点一定在 数组最末端，并且可以用根结点在前面的元素中找一个分界点，其 左边的元素均小于root， 右边的元素均大于root 。
2. 步骤是范围定在 0 ~ sq.size() - 1，然后从头开始找 左右子树的分界点k ，k就是右子树的第一个元素的下标。只要左边的元素满足小于root，右边的元素满足大于root，即可。如果否，返回false。
3. dfs的边界条件是 l, k - 1和k, r - 1。之所以是 r - 1是因为r已经是根结点了，并且递归需要不断缩小范围，l是一直不变的，r每次递归都会向左边减1。所以是r - 1。

复杂度分析：

二叉树的每个节点只会被遍历一次，所以时间复杂度为O(n)

C++代码实现：

class Solution {
public:
    vector sq;
    bool dfs(int l, int r)
    {
        if(l >= r) return true;
        int k = l;
        while(k < r && sq[k] < sq[r]) k ++;
        for(int i = k; i < r; i ++)
            if(sq[i] < sq[r])
                return false;
        return dfs(l, k - 1) && dfs(k, r - 1);
    }

    bool verifySequenceOfBST(vector sequence) {
        sq = sequence;
        return dfs(0, sq.size() - 1);
    }
};

六分钟学算法第一季渐渐走入尾声了，但剑指offer系列将后续持续更新，考虑到很多算法比赛的题目也非常经典，下一季我们将围绕一些常见的比赛题进行算法的学习。 复盘这段时间的算法练习，你是否有了对算法更加深刻的认识呢？是否有很多收获呢？第一季共34篇，这是本季的最后完结篇，算法之旅永无止境！ 第二季将在不久的八月开启，我们下季再会！

---