在递归中分配局部变量

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

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)

有什么建议吗？

来源

2013-02-04 Jack F

首先，修复压痕。 – abarnert

接下来，局部变量的全部要点在于它对当前函数调用是本地的。你到底想要什么？如果您想将值传回并备份，则需要将其最大化为一个参数（默认值为1）。如果你想将它绑定到一个闭包，你需要一个内部函数（使用'nonlocal'，一个可变的默认参数等）。 – abarnert

我想要一个变量来跟踪我的最高值，那它 –

你并不需要保持最大值的变量在所有递归调用，并通过各种手段，不是全球之一。在一个结构良好的递归中，结果将在每个递归调用的返回值中传递。这样的：上面

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可以为null，则调用前tree_max()检查此条件。

来源

2013-02-04 23:26:50

但它是如何知道哪个是最大值返回 –

@JackF：你将它传递给递归链。 – abarnert

@JackF看到我更新的答案，看看我的意思 –

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

def tree_max(node, max=None):

来源

2013-02-04 23:24:53

我想要一个遍历树的生成器。这意味着你可以写一个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)

来源

2013-02-04 23:41:15

+1。更好。或者，在Python 3.3中，只是'从tree_traverse（node.left）产生'而不是循环。但它可能比OP所寻找的更为激进的变化。 – abarnert

@abarnert，因为几乎没有人使用Python3.3，所以我不打算麻烦，但是我会添加它以使答案在未来更加有用。 –

根据我的经验，使用3.3的人比3.0-3.2的人多。（但仍然不到2.7，不幸...） – abarnert

在递归中分配局部变量

回答

相关问题