>我正在尝试编写一个函数，该函数返回二叉树中的最小值，而不是二叉搜索树。这是我写的，这是不正确的。
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(root.left, min_t)
min(root.right, min_t)
return min_t
我觉得我不太了解递归。我似乎无法弄清楚何时将 return 语句与递归调用一起使用，何时不使用。
感谢您的见解！
这是我想出的另一个，它有效，但似乎不是最有效的：
n = []
def min_tree(root, n):
if root:
n += [(root.key)]
min_tree(root.left, n)
min_tree(root.right, n)
return min(n)
思潮？
迈克尔的回答解释了你可能应该处理这个问题的方式，但他没有解释你目前的尝试有什么问题。据我了解，您的策略是检查每个节点，并随时跟踪最低值，使用递归查找所有节点。检查完所有节点后，您就知道结果是整个树的最小值。这是一个完全有效的方法，除了参数没有完全按照你期望的方式工作之外，它会起作用。
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
对于此特定问题，您希望遍历整个树并返回看到的最小值。 但总的来说，递归的基本原理是，然后你再次调用函数，你会看到同一问题的修改版本。
考虑你的树：
root
/
left right
当您调用左侧子树上的递归函数时，您将再次看到一棵树。 因此，您应该能够使用相同的逻辑。
递归函数的关键是基本情况和递归步骤。 在你的树示例中，基本情况不是当你找到最小值时（你怎么知道？），而是当你到达树的底部（又名叶子）时。
而且，您的递归步骤是查看每个子问题（bin_min（左）和bin_min（右））。
最后一块是考虑返回值。 不变性是你的函数返回了它看到的最小元素。 因此，当你的递归调用返回时，你知道它是最小的元素，然后你需要返回的是三个可能的选择（根、left_min和right_min）中的最小元素。
def min_bin(root):
if not root:
return MAX_VAL
left_min = min_bin(root.left)
right_min = min_bin(root.right)
return min(left_min, right_min, root.val)
请注意，这是一个与@Rik Poggi的解决方案不同的解决方案。 他使用尾递归来优化它。
因为尝试自己解决这个问题会比罐头解决方案获得更多，所以这里有一些提示。首先，你不应该称它为min，因为当然你不能调用python的min来测试你的结果。正如迈克尔的回答提醒我的那样，你不必通过min_t，因为你可以测试root.key - 但我认为通过min_t来理解问题是有帮助的。
除此之外，你的第一行刚刚好;这里做得很好。
def tree_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.第二个是right子树的最小值。第三个是left子树的最小值。获取后两个值（这是递归调用出现的地方），然后返回最小值。
下面是一个查找最小元素的递归方法：
minelement = float("inf")
def minimum(self, root):
global minelement
if root:
if root.data < minelement:
minelement = root.data
self.minimum(root.left)
self.minimum(root.right)
return minelement