检查给定的遍历是否有效的BST [英] Checking if given preorder traversal is valid BST

问题描述

我正在编写代码以检查预购遍历是否为有效的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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！