迈克尔的回答解释了您可能应该解决问题的方式,但他没有解释您当前的尝试有什么问题。据我了解,您的策略是检查每个节点,并随时跟踪最低值,使用递归查找所有节点。一旦检查了所有节点,您就会知道结果是整个树的最小值。这是一种完全有效的方法,它本来可以奏效的,只是论点不像您预期的那样有效。
Python 按值传递参数,而不是按引用传递。当您使用“min_t = root.key”为 min_t 赋值时,它只在函数内部生效。函数的调用者看不到新值。
您可以使用一些更简单的代码对此进行测试:
def add_one_to(x):
x = x + 1
print "add_one_to", x
x = 2
add_one_to(x)
print x
当您运行代码时,您可以看到 x 在函数内部递增,但在顶层没有递增。
这也适用于函数调用自身时。每个调用都有自己的一组局部变量,并且分配给函数内部的局部变量不会影响调用它的实例。
请注意,某些语言确实允许您通过引用传递参数。如果您通过引用传递参数,那么在函数内部分配该参数也会影响调用者。如果 Python 是其中一种语言,您可以将 min_t 作为参考参数,并且您的函数将正常工作。
虽然 Python 不直接支持引用参数,但您也可以将引用参数视为在函数被调用时进入函数并在函数完成时传递回调用者的值。你可以分别做这两件事。要将值传递回调用者,请返回该值。然后调用者可以将该函数分配给它的本地函数,并且您基本上已经通过引用传递了一个参数。
以下是如何将其应用于上面的示例:
def add_one_to(x):
x = x + 1
print "add_one_to", x
return x
x = 2
x = add_one_to(x)
print x
只需添加一个返回值和赋值,它就可以正常工作。
您也可以将其应用于您的原始功能:
def min(root, min_t): # min_t is the initially the value of root
if not root:
return min_t
if root.key < min_t:
min_t = root.key
min_t = min(root.left, min_t)
min_t = min(root.right, min_t)
return min_t
我所做的只是在每次调用 min() 之前添加“min_t =”,并将您的 return 语句更改为最后返回 min_t。(我认为您可能无论如何都打算返回 min_t。min 是您的函数的名称,所以这没有多大意义。)我相信该版本会起作用。
编辑:尽管如此,您的 min_tree 函数起作用的原因是 n 是一个列表,而列表是可变对象。当我在上面谈论“价值观”时,我真正的意思是“对象”。python 中的每个变量名都映射到一个特定的对象。如果你有这样的代码:
def replace_list(x):
x = [1, 2, 3]
x = [2]
replace_list(x)
print x
结果是[2]。因此,如果您使用“x =”为 x 分配一个新值,调用者将看不到它。但是,如果您这样做:
def replace_list(x):
x.append(1)
x = [2]
replace_list(x)
print x
结果是 [2, 1]。这是因为你没有改变 x 的值;x 仍然指向同一个列表。但是,该列表现在包含一个附加值。不幸的是,“+=”运算符在这方面令人困惑。您可能认为“x += y”与“x = x + y”相同,但在 Python 中并非总是如此。如果“x”是一种专门支持“+=”的对象,那么该操作将修改该对象。否则,它将与“x = x + 1”相同。列表知道如何处理“+=”,因此将 += 与列表一起使用会就地修改它,但与数字一起使用则不会。
您实际上可以在不进行任何函数调用的情况下对其进行测试:
x = [1, 2]
y = x
y += [3]
print x # [1, 2, 3]
print y # [1, 2, 3]
print x is y # True, x and y are the same object, which was modified in place
x = [1, 2]
y = x
y = y + [3]
print x # [1, 2]
print y # [1, 2, 3]
print x is y # False, y is a new object equal to x + [3]
x = 1
y = x
y += 2
print x # 1
print y # 3
print x is y # False, y is a new object equal to x + 2