题目描述

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

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

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

样例

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

输出：true

算法

(二叉搜索树，递归) $O(n^2)$

假设数组 $seq$ 下标区间为 $[l, r]$
因为是后序遍历，所以可以确定最后一个元素是整棵二叉搜索树的根，下标为 r

从前往后扫描找到最后一个小于根的数就是根的左孩子，下标为 k，则左子树下标区间为 $[l, k]$
则右子树下标区间为 $[k + 1, r - 1]$，则判断区间中的元素是否都大于根节点 $seq[r]$
如果不是，说明由后序序列推出的不是一棵二叉搜索树，否则递归判断左子树和右子树是否是一根二叉搜索树

时间复杂度

递归中的 while 循环会遍历左子树，for 循环最坏情况下会遍历右子树，所以一次递归是 $O(n)$，一共进行 n 次递归，所以时间复杂度是 $O(n^2)$

C++ 代码

class Solution {
public:
    vector<int> seq;

    bool verifySequenceOfBST(vector<int> sequence) {
        seq = sequence;
        if (seq.empty()) return true;
        return dfs(0, seq.size() - 1);
    }

    bool dfs(int l, int r) {
        if (l >= r) return true;
        // 右端点是根
        int root = seq[r];
        int k = l;
        // 找到根的左孩子（左子树的根）
        while (k < r && seq[k] < root) k ++ ;
        // 判断 root 的右子树是否都大于 root，如果存在小于 root 的元素，说明不是一根二叉搜索树
        for (int i = k; i < r; i ++ ) 
            if (seq[i] < root)
                return false;
        // 否则递归判断左子树和右子树是否都满足二叉搜索树的定义
        return dfs(l, k - 1) && dfs(k, r - 1);
    }
};