在樹遞歸期間保存路徑

我陷入了一個令人討厭的問題：我有一棵樹並且想遞歸遍歷它。在遞歸期間，我想保存當前路徑，因爲在節點中只保存當前值。我用下面的代碼是：在樹遞歸期間保存路徑

def getPaths(tree, level, path): 
    copyPath = list(path) 
    if level > 1: 
     if not tree.children: 
      '''do some non important stuff''' 
    for child in tree.children: 
     copyPath.append(child.data.value) 
     getPaths(child,level+1, copyPath)

首先我想簡單地做沒有複製列表，但是這顯然不能工作。但即使我複製列表，似乎只使用一個全局列表來收集所有的值，而不是將它們按順序收集到不同的列表中。

我希望對這個（可能）簡單的問題有所幫助。

來源

2014-03-27 kai.dannies

由於性能方面的原因（你不會喜歡另一種方式！），但是你可以使用不同的數據結構，或者使用不同的數據結構。如果你想，只需保留一份清單。 –

如果你想這樣做在一個不變的風格，放眼itertools和chain方法：

for child in tree.children: 
    getPaths(child, level+1, chain(path, [child.data.value]))

現在你有一個iterator，你可以遍歷這是依賴不是複製列表而是代表最初「路徑」加上新的「節點」的東西。

編輯：

只要記住，你是在處理一個iterator因此，如果你希望能夠在其上進行迭代，然後傳遞給另一個函數，您可能希望tee它（也itertools）。

來源

2014-03-27 14:32:34 wheaties

謝謝你的快速回答。適用於我:)。祝你今天愉快 –

在樹遞歸期間保存路徑

回答

相關問題