问题描述
我正在编写代码以检查预购遍历是否为有效的BST。
，例如预订遍历 1,2,4,3,5 是有效的BST，而 1,3,4,2 不是
I was writing code to check from preorder traversal if it is a valid BST. e.g preorder traversal 1,2,4,3,5 is valid BST while 1,3,4,2 is not
我从该预定顺序中构建了整棵树，然后检查该树是否为有效的BST。这是关于时间和空间复杂度的 O（N）解决方案。
I built whole tree from that preorder sequence and then checked if that tree is a valid BST. This is O(N) solutions with respect to both space and time complexity.
有没有人比这更好的方法？这个？我有直觉，我们可以在O（1）的额外空间中执行此操作。
Does anybody have good approach than this? I have intuition that we can do this in O(1) extra space.
推荐答案
检查是否排列1..n是有效BST的前置符（如果存在，则表示BST是唯一的；由于第二次重构未排序，因此imreal的答案不是反例）等效于测试该排列是否可堆叠排序，即避免使用231-图案。在这些名称中，我似乎找不到任何线性时间恒定空间算法，考虑到这个问题引起了人们的关注，没人知道一个恒定的额外空间解决方案，这似乎会暗示这一点。
Checking whether a permutation of 1..n is a preorder of a valid BST (that BST, if it exists, is unique; imreal's answer is not a counterexample because the second reconstruction is not sorted) is equivalent to testing whether that permutation is stack-sortable, i.e., avoids the 231-pattern. I can't seem to find any linear-time constant-space algorithm under any of these names, which would tend to suggest given the amount of attention that this problem has attracted that no one knows of a constant extra space solution.
如果您愿意承担可以销毁的读/写输入，那么可以使用线性时间算法，该算法使用恒定的额外空间。无需分别重建树然后对其进行测试。
If you're willing to assume a read/write input that can be destroyed, then there's a linear-time algorithm that uses constant extra space. It's not necessary to reconstruct the tree separately and then test it. Here's some Python to that effect.
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
要消除堆栈的单独存储，请将其存储在输入列表的前缀中。
To eliminate the separate storage for the stack, store it in a prefix of the input list.
这篇关于检查给定的遍历是否有效的BST的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！