跟着姚桑学算法-二叉搜索树的后序遍历序列

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

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

如果是则返回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<int> 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<int> sequence) {
        sq = sequence;
        return dfs(0, sq.size() - 1);
    }
};