验证树是否为二叉搜索树 Python

Question

我有一个练习面试的问题，要求我验证一棵树是否是平衡搜索树，并给出验证的方法……我有一个类定义如下：

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

我遇到的问题是，当我尝试实现这个验证方法时，总是得到错误的结果，即使我试图创建一棵有效的搜索树。我的实现如下：

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. 首先，在tree_min函数中，你检查子节点是否为null的顺序是反的。也就是说，你在访问node.left之前检查node.right是否存在，反之亦然。

2. 第二，当在叶子节点上调用tree.min时，它会返回负无穷大。在计算最小值时，你需要使用正无穷大（在最大值的计算中，负无穷大是正确的）。

3. 第三，在verify函数中，你有一个逻辑错误，它不加条件地调用tree_min或tree_max，甚至在它的子节点是None的情况下也会调用。我建议让所有函数都能处理传入None的情况，而不是依赖调用者来做正确的事情。这样也能让min和max的代码简单一些！

4. 最后，你在比较node.value，也就是你给每个节点的字符串。我怀疑你其实想用node.key来比较。将浮点数（比如float("-inf")）和字符串（比如"ten"）进行比较在Python 3中是错误的，即使在Python 2中是合法的，它的表现也可能和你预期的不一样。

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

最后，还有一些小的风格问题（虽然不是bug，但仍然可以改进）。Python支持链式比较，所以你可以把verify中的第一个if语句简化为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