字符串值而不是在遞歸過程中打印

Question

因此，我寫了這段代碼來打印二叉樹的所有根葉子路徑，當它打到基本情況時，它會打印每個路徑，而我想將它存儲在列表，以便最後我有一個列表包含每個路徑。我已經嘗試了幾個使用尾遞歸或使用其他全局列表的東西，但我無法正確實現它。

def rootleafPath(self, root): 
    global arr 
    if root is None: 
     return 
    arr.append(root.rootid) 
    if self.isLeaf(root): 
     print arr 
    self.rootleafPath(root.left) 
    self.rootleafPath(root.right) 
    arr.pop() 

這將返回

[1, 2, 4] 
[1, 2, 5] 
[1, 3] 

，而我希望我的函數返回，例如[[1，2，4]，[1，2，5]，[1,3]

列表

我在大多數遞歸解決方案中都遇到了這個問題，我需要在打到基本案例而不是打印時存儲結果。

Answer 1

您的遞歸路徑算法應該在每個步驟返回列表的列表。如果你在一個葉節點上，它應該返回一個包含該節點ID的列表。否則，它應該將當前節點的ID添加到由左或右節點返回的每個列表中，然後返回這個新列表。排序很難解釋，所以我寫了一些代碼:)

class Node(object): 
    def __init__(self, root_id, left=None, right=None): 
     self.root_id = root_id 
     self.left = left 
     self.right = right 
    def is_leaf(self): 
     if self.left or self.right: 
      return False 
     return True 

def path(node): 
    if node.isLeaf(): 
     return [[node.root_id]] 
    left_paths = [[node.root_id] + p for p in path(node.left)] if node.left else [] 
    right_paths = [[node.root_id] + p for p in path(node.right)] if node.right else [] 
    return left_paths + right_paths 

tree = Node(0,Node(1, Node(2), Node(3, right=Node(4))), Node(5, Node(6))) 

path(tree) => [[0, 1, 2], [0, 1, 3, 4], [0, 5, 6]] 

使用全局陣列是困難的，因爲在遞歸的每一層，你必須知道程序的狀態。這是更容易打破問題分爲兩個步驟：

1. 如果我在一個葉子結點，我有什麼返回表示樹如果葉節點是樹中的唯一節點
2. 如果我與孩子在一個節點上，他們應該返回給我什麼，以便我可以充分代表我的子樹。

在這種情況下，葉節點應該返回包含一個列表的列表它的ID： 返回[node.root_id]

而且，如果節點是樹中的某個地方，它應該期待從其子女描述子樹的列表清單。然後它應該添加它的id作爲每個子列表的第一個元素，然後返回其所有子列表的連接結果。

我希望這有助於！