3

我有一棵树，它不是二叉树，所以我想比较所有节点并使用递归返回最大的节点。我有一个如何跟踪它的问题，因为我不能放置一个全局变量，因为它必须是本地的......我猜......但是如果递归进行，它会重置局部变量。

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)

有什么建议么？

4

3 回答 3

4

您不需要在所有递归调用中将最大值保留在变量中，并且无论如何，不​​是全局变量。在结构良好的递归中，结果将在每个递归调用的返回值中传递。像这样：

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

于 2013-02-04T23:26:50.513 回答
3

我会有一个遍历树的生成器。这意味着您可以在不重复遍历逻辑的情况下编写 amin()等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)
于 2013-02-04T23:41:15.897 回答
1

这通常使用关键字参数来完成，例如

def tree_max(node, max=None):
于 2013-02-04T23:24:53.797 回答