检查给定的前序遍历是否有效BST

Question

如果它是一个有效的BST,我正在编写代码来检查preorder遍历.例如,preorder遍历1,2,4,3,5 是有效的BST而1,3,4,2不是

我从该预订序列构建了整个树,然后检查该树是否是有效的BST.这是O(N)关于空间和时间复杂性的解决方案.

有人有比这更好的方法吗？我有直觉,我们可以在O(1)额外空间中做到这一点.

Answer 1

检查1..N的排列是否是一个有效的BST的前序(即BST,如果存在,是独一无二的; IMREAL的答案不是一个反例,因为第二重建未排序)等同于测试该排列是否是栈-sortable,即避免231模式.我似乎无法在任何这些名称下找到任何线性时间常数空间算法,这将倾向于表明这个问题引起的注意力,没有人知道恒定的额外空间解决方案.

如果您愿意假设可以销毁的读/写输入,那么有一个使用恒定额外空间的线性时间算法.没有必要单独重建树然后测试它.这是一些Python的效果.

def isbstpreorder(iterable):
    lowerbound = None
    stack = []
    for x in iterable:
        if lowerbound is not None and x < lowerbound: return False
        while stack and stack[-1] < x: lowerbound = stack.pop()
        stack.append(x)
    return True

要消除堆栈的单独存储,请将其存储在输入列表的前缀中.