6

我有一个练习面试问题，它告诉我验证一棵树是否是平衡搜索树并给出验证方法......我的课程是

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 树，我似乎总是会出错。我的实现如下：

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)

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

4

1 回答 1

8

我在您的代码中看到四个错误。

  1. 首先，您对 null 孩子的检查是向后的tree_min。也就是说，您node.right在访问之前检查是否存在node.left，反之亦然。

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

  3. 第三，您在 中存在逻辑错误verify，因为它在其子节点上无条件调用tree_minortree_max和自身，即使其中一个或两个是None. 我建议让所有函数处理被传递None，而不是依赖调用者来做正确的事情。这也稍微简化了min代码！max

  4. 最后，您正在对 进行比较node.value，这是您为每个节点提供的字符串。我怀疑你想比较 using node.key。将浮点数 (like float("-inf")) 与字符串 (like "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
于 2013-02-14T21:54:59.777 回答