performance - 是否有确定后序序列是否为有效 BST 的线性解决方案？

Question

问题:给定一个整数数组，判断它是否可以是 BST 的后序遍历序列。例如:[5, 7, 6, 9, 11, 10, 8] 返回 true，但 [7, 4, 6, 5] 返回 false。

我想知道我们是否可以在线性时间内完成此操作。以下是我想出的针对 N^2 和 NlgN 的解决方案。

N^2 解法:遍历数组，检查根的左右子树值是否分别小于和大于根的值。对每个子树重复。

NlgN 解决方案:构建一个从输入数组的右到左的 BST。跟踪我们随时可能遇到的最大数量。每次我们插入左 child 时，这个最大数量都会更新到父节点。如果我们尝试插入一个大于跟踪的最大数量的节点，我们可以返回 false。

Answer 1

这是一个线性时间算法，它比这个答案的最后一个版本简单得多。

def checkbst(lst):
    # stack contains the values of nodes from which the current path departs right
    stack = [float('-inf')]
    # upperbound is the value of the leafmost node from which the path departs left
    upperbound = float('inf')
    for x in reversed(lst):
        # pop stack elements greater than or equal to x
        # stack[-1] is the top
        while stack[-1] >= x:
            upperbound = stack.pop()
        if x >= upperbound:
            return False
        # push
        stack.append(x)
    return True

可以想象一个使用根值最后出现这一事实的递归过程，如下所示。从右到左扫描，直到找到小于根的值。在该值之后拆分数组的最大适当前缀。递归验证右半部分。验证左半部分的值是否都小于根，然后递归验证这一半。

后面的递归在尾部位置，可以转为迭代。可以推迟对值小于根的检查，因为上限随时间单调递减。我们将递归堆栈的剩余部分保留在 stack 中，即我们从中进行非尾递归的根值序列。内部循环确定调用堆栈中有多少应该考虑当前元素。它是摊销常数时间。