执行二叉树代码时出现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 145Assignment 8a8q1.py", line 44, in largest_leaf_value
if lres > res:
TypeError: '>' not supported between instances of 'NoneType' and 'int'

请告诉我为什么会发生这种情况?

Answer 1

由于您的largest_leaf_value将在其递归基本情况下返回None，因此您需要为lres或rres准备好将None分配给它们。

类型错误发生在比较lres或rres与res的行上，并且告诉您None的值不能与res比较。

所以你有两种可能性:要么避免在lres或rres为None时执行比较，要么不让你的函数返回None，而是返回-无穷大(因为该值小于所有其他有限数值)。

第一种方法的解:

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))
)