执行二叉树代码时出现TypeError

Question

我在测试以下功能时遇到错误。有人可以帮我解决这个问题吗？

代码：

class treenode(object):

def __init__(self, data, left=None, right=None):
    self.data = data
    self.left = left
    self.right = right
    
def largest_leaf_value(tnode):
    if tnode is None:
        return None
    res = tnode.data
    lres = largest_leaf_value(tnode.left)
    rres = largest_leaf_value(tnode.right)
    if lres > res:
        res = lres
    if rres > res:
        res = rres
    return res

这是测试脚本：

# test tree with 1 level i.e. root value only
input_tree = T.treenode(1)
expected = 3

result = a8q1.largest_leaf_value(input_tree)
assert result is expected, "{}: copying empty tree returned unexpected result".format(test_item)

# test a longer tree
input_tree = T.treenode(1, T.treenode(2, T.treenode(3, T.treenode(4, T.treenode(5)))))
expected = 5

result = a8q1.largest_leaf_value(input_tree)
assert result is expected, "{}: copying empty tree returned unexpected result".format(test_item)

这是我遇到的错误：

Traceback (most recent call last):
  File "D:/CMPT 145/Assignment 8/a8q1_testing.py", line 60, in <module>
    result = a8q1.largest_leaf_value(input_tree)
  File "D:\CMPT 145\Assignment 8\a8q1.py", line 44, in largest_leaf_value
    if lres > res:
TypeError: '>' not supported between instances of 'NoneType' and 'int'

请告诉我为什么会这样？

Answer 1

由于您的 largest_leaf_value 将 return None 在其递归基本情况下，您需要为 lres 或 rres 做好准备以获得 None分配给他们。

类型错误发生在您将 lres 或 rres 与 res 进行比较的行上，并告诉您 None 值无法与 [= 进行比较20=].

所以你有两种可能性：要么避免在 lres 或 rres 为 None 时执行比较，要么不要让你的函数 return None，而是 return -infinity（因为该值小于所有其他有限数值）。

第一种方法的解决方案：

def largest_leaf_value(tnode):
    if tnode is None:
        return None
    res = tnode.data
    lres = largest_leaf_value(tnode.left)
    rres = largest_leaf_value(tnode.right)
    # Only compare when not None:
    if lres is not None and lres > res:
        res = lres
    if rres is not None and rres > res:
        res = rres
    return res

第二种方法的解决方案：

def largest_leaf_value(tnode):
    if tnode is None:
        # Don't return None, but -infinity
        return float("-inf")
    res = tnode.data
    lres = largest_leaf_value(tnode.left)
    rres = largest_leaf_value(tnode.right)
    if lres > res:
        res = lres
    if rres > res:
        res = rres
    return res

请注意，当您在初始调用中将空树（即 None）作为参数传递时，其行为会有所不同。从数学上讲，它没有定义空集合中的最大值是多少，因此这将取决于您期望在这种情况下发生什么。

最后，你可以使用max()让第二个版本更短一点：

def largest_leaf_value(tnode):
    return (float("-inf") if tnode is None else
        max(tnode.data, largest_leaf_value(tnode.left), largest_leaf_value(tnode.right))
    )

执行二叉树代码时出现TypeError

TypeError while executing Binary tree code

python

binary-search-tree