字符串值而不是在递归过程中打印

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作为每个子列表的第一个元素，然后返回其所有子列表的连接结果。

我希望这有助于！