在遞歸中分配局部變量

我有一棵樹，它不是二叉樹，所以我想比較所有的節點並使用遞歸返回最大的一個節點。我有一個如何跟蹤它的問題，因爲我不能放置一個全局變量，因爲它必須是本地的...我猜...但是，如果遞歸去重置局部變量。在遞歸中分配局部變量

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

在遞歸中分配局部變量

回答

相關問題