递归中赋值局部变量

Question

我有一棵树，但它不是二叉树，所以我想比较所有的节点，找出最大的那个，打算用递归的方法来实现。不过我遇到了一个问题，就是怎么记录这个最大值，因为我不能用全局变量，得用局部变量……我想是这样。但如果用局部变量的话，递归的时候它会被重置。

def tree_max(node):
    max=1                                                                                     
    if node.left == None and node.right == None:
       if node.value>max:
          max=node.value
          return max
    elif node.left == None and node.right != None:
        return tree_max(node)
    elif node.left != None and node.right == None:
        return tree_max(node.left)
    else:
        return tree_max(node.left)

有什么建议吗？

Answer 1

这通常是通过关键字参数来实现的，比如说：

def tree_max(node, max=None):

Answer 2

我会创建一个生成器来遍历树。这意味着你可以写出像 min()、sum() 这样的函数，而不需要重复遍历树的逻辑。

def tree_traverse(node):
    if not node.left and not node.right: # if only leaf nodes have values
        yield node.value
    if node.left:
        for v in tree_traverse(node.left):
            yield v
    if node.right:
        for v in tree_traverse(node.right):
            yield v

现在你只需要使用 max(tree_traverse(node)) 就可以了。

如果所有的节点都有值，你可以省略第一个 if，并把 yield 的缩进减少。

正如 @abarnert 所说，Python3.3 提供了一种很好的方法来简化递归生成器。

def tree_traverse(node):
    if not node.left and not node.right: # if only leaf nodes have values
        yield node.value
    if node.left:
        yield from tree_traverse(node.left)
    if node.right:
        yield from tree_traverse(node.right)

Answer 3

在递归调用中，你不需要在一个变量里保存最大值，更不需要用一个全局变量。在结构良好的递归中，结果会通过每次递归调用的返回值来传递。就像这样：

def tree_max(node):
    maxleft  = float('-inf') if not node.left  else tree_max(node.left)
    maxright = float('-inf') if not node.right else tree_max(node.right)
    return max(node.value, maxleft, maxright)

上面的代码假设 node 不是 None，如果 node 可能是空的，那么在调用 tree_max() 之前要先检查这个条件。