我寫過/看過一些recursive functions. 我的問題是，在很多問題中，我們經常被要求保留'count'一些東西，例如“計算二叉樹中葉節點的數量”。
一種遞回函式是：
def countLeavesInTree(root, count= 0):
if root.left:
countLeavesInTree(root.left, count)
if root.right:
countLeavesInTree(root.right, count)
if not root.left and not root.right:
count = 1
return #How can we increment count by 1 here?- is this right?
return count
與上述等效，我看到遞回遞增'count'如下：
def countLeavesInTree(root):
count = 0
if root.left:
count = countLeavesInTree(root.left)
return
if root.right:
count = countLeavesInTree(root.right)
return
if not root.left and not root.right:
return 1
return count
我們什么時候使用第一種方法，什么時候使用第二種方法？還是沒關系，兩者都可以在任何情況下使用？
修改后的代碼：
def countLeavesInTree(root):
count = 0
if not root.left and not root.right:
return 1
else:
count = countLeavesInTree(root.left) countLeavesInTree(root.right)
return count
uj5u.com熱心網友回復：
您的“修改后的代碼”非常接近，您唯一需要添加的是后衛以確保您不會將 aNone作為新的root.
你要：
def countLeavesInTree(root):
if not root.left and not root.right:
return 1
count = 0
if root.left:
count = countLeavesInTree(root.left)
if root.right:
count = countLeavesInTree(root.right)
return count
或者通過理解，您可能會：
def countLeavesInTree(root):
if not root.left and not root.right:
return 1
return sum(
countLeavesInTree(child)
for child
in [root.left, root.right]
if child
)
一個完整的簡單示例可能是：
class Node:
def __init__(self, val):
self.left = None
self.right = None
self.value = val
root = Node("root")
root.left = Node("root.left")
root.left.left = Node("root.left.left") # a leaf
root.right = Node("root.right")
root.right.right = Node("root.right.right") # a leaf
root.right.left = Node("root.right.left") # a leaf
def countLeavesInTree(root):
if not root.left and not root.right:
return 1
return sum(countLeavesInTree(child) for child in [root.left, root.right] if child)
print(countLeavesInTree(root))
幸運的是，這應該給你3。
在進行遞回時，您真的永遠不想嘗試像第一個版本一樣維護全域。Python 遞回不是很好（因為您可以意外地相當快地達到默認限制），因此如果您想嘗試維護這樣的變數，最好嘗試從遞回轉移到更傳統的回圈結構。
也許是這樣的：
def countLeavesInTree2(root):
if not root:
return 0
count = 0
brush_pile = [root]
while brush_pile:
current = brush_pile.pop(0)
if not current.left and not current.right:
count = 1
else:
brush_pile.extend(
child
for child
in [current.left, current.right]
if child
)
return count
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/356400.html
上一篇：球拍彩虹形狀遞回