在二叉树中查找最小值，Python

Question

我正在尝试编写一个函数，它返回二叉树中的最小值而不是一个二叉搜索树。 这是我写的，不对。

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)

有什么想法？

Answer 1

对于这个特殊的问题，您需要遍历整个树并返回看到的最小值。但是一般来说，递归的基本原理是，当你再次调用这个函数时，你会遇到同样问题的一个修改版本。

想想你的树：

    root
   /    \
left   right

当您调用左子树上的递归函数时，您将再次看到一棵树。因此，您应该能够使用相同的逻辑。

递归函数的关键是基本情况和递归步骤。在您的树示例中，基本情况不是在找到最小值时（您如何知道？）而是当你到达树的底部（又称叶子）。

而且，递归步骤是查看每个子问题（bin_min（左）和bin_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的解决方案。他使用尾部递归来优化它。

Answer 2

迈克尔的回答解释了你处理问题的方式，但他没有解释你目前的尝试有什么问题。据我所知，您的策略是检查每个节点，并在运行时跟踪最低值，使用递归查找所有节点。检查完所有节点后，就知道结果是整个树的最小值。这是一个非常有效的方法，而且它本来会起作用的，只是论点并不像你期望的那样起作用。

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语句更改为return 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

Answer 3

因为比起罐装的解决方案，你能从自己的努力中得到更多，这里有一些提示。首先，您不应该调用它min，因为当然，您不能调用python的min来测试结果。正如Michael的回答提醒我的那样，你没有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子树的最小值。获取后两个值（这是递归调用进入的地方），然后返回最小的值。