python - 验证一棵树是否是 bst Python

Question

我有一个面试练习题，告诉我验证一棵树是否是平衡搜索树，并给出验证方法......我的类(class)为

Class Node:
def __init__(self, k, val):
    self.key = k
    self.value = val
    self.left = None
    self.right = None

树的最大值和最小值的其他函数定义为

def tree_max(node):
    maxleft  = float('-inf') if not node.left  else tree_max(node.left)
    maxright = float('-inf') if not node.right else tree_max(node.right)
    return max(node.value, maxleft, maxright)

def tree_min(node):
    minleft  = float('-inf') if not node.right else tree_min(node.left)
    minright = float('-inf') if not node.left else tree_min(node.right)
    return min(node.value, minleft, minright)

我的验证方式为

def verify(node):
    if tree_max(node.left) <= node.value and node.value <= tree_min(node.right):
       if verify(node.left) and verify(node.right):
           return True
       else:
           return False
    else:
        return False

当我尝试实现验证方法时，我的问题出现了，即使我尝试制作 BST 树，我似乎总是得到 false。我的实现如下:

root= Node(10, "Hello")
root.left = Node(15, "Fifteen")
root.right= Node(30, "Thirty")

print verify(root)

root = Node(10, "Ten")
root.right = Node(20, "Twenty")
root.left = Node(5, "Five")
root.left.right = Node(15, "Fifteen")

print verify(root)

两者都给我错误...我的验证功能或我的最小/最大功能是否有问题...任何帮助将不胜感激。

Answer 1

我在您的代码中发现了四个错误。

1. 首先，您对 null 子项的检查在 tree_min 中倒退了.也就是说，您正在检查是否 node.right在访问之前存在 node.left ，反之亦然。

2. 第二，tree.min在叶节点上调用时返回负无穷大。您需要在最小计算中使用正无穷大(负无穷大在最大版本中是正确的)。

3. 第三，你在verify里面有逻辑错误，因为它无条件调用 tree_min或 tree_max和它自己在它的子节点上，即使它们中的一个或两个都是 None .我建议让所有函数处理被传递 None ，而不是依赖调用者做正确的事情。这也简化了 min和 max一点代码!

4. 最后，您要对 node.value 进行比较，这是你给每个节点的字符串。我怀疑您想使用 node.key 进行比较反而。将 float (如 float("-inf") )与字符串(如 "ten" )进行比较在 Python 3 中是错误的，即使在合法的 Python 2 中，它也可能无法像您预期的那样工作。

解决了这些问题后，我在创建有效和无效的树时得到了预期的结果。你的两个例子都是无效的，所以如果你用它们来测试，你总是会得到一个 False结果。

最后，几个小的样式问题(不是错误，但仍然可以改进)。 Python 支持链式比较，所以你可以简化你的第一个 if verify 中的声明至 tree_max(node.left) <= node.key <= tree_min(node.right) .您可以通过将检查与 and 连接起来进一步简化这部分代码。而不是嵌套额外的 if声明。

这是适合我的代码版本(使用 Python 3，但我认为它完全向后兼容 Python 2):

class Node:
    def __init__(self, k, val):
        self.key = k
        self.value = val
        self.left = None
        self.right = None

def tree_max(node):
    if not node:
        return float("-inf")
    maxleft  = tree_max(node.left)
    maxright = tree_max(node.right)
    return max(node.key, maxleft, maxright)

def tree_min(node):
    if not node:
        return float("inf")
    minleft  = tree_min(node.left)
    minright = tree_min(node.right)
    return min(node.key, minleft, minright)

def verify(node):
    if not node:
        return True
    if (tree_max(node.left) <= node.key <= tree_min(node.right) and
        verify(node.left) and verify(node.right)):
        return True
    else:
        return False

root= Node(10, "Hello")
root.left = Node(5, "Five")
root.right= Node(30, "Thirty")

print(verify(root)) # prints True, since this tree is valid

root = Node(10, "Ten")
root.right = Node(20, "Twenty")
root.left = Node(5, "Five")
root.left.right = Node(15, "Fifteen")

print(verify(root)) # prints False, since 15 is to the left of 10