python - 在递归期间将值字符串化而不是打印它们

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. 如果我位于有 child 的节点，他们应该返回给我什么，以便我可以完全代表我的子树。

在这种情况下，叶节点应该返回包含其 id 的单个列表的列表: 返回[[node.root_id]]

如果节点位于树内部的某个位置，它应该期望来自其子节点的描述子树的列表列表。然后，它应该将其 id 添加为每个子列表的第一个元素，然后返回其所有子列表的串联结果。

希望这会有所帮助!