python - Python：获取树中所有可能路径的列表？

Question

我有一棵树，例如看起来像这样

 (0, 1)
    (2, 3)
       (4, 5)
          (6, 7)
          (6, 3)
       (4, 1)
          (6, 3)

当我用这种方法打印它时：

def deep_print(self, d=0):
    if self == None:
        return

    print("   "*d, self.value)

    for child in self.children:
        child.deep_print(d + 1)

现在我想要一个方法，它给我一个叶子所有可能方法的列表。所以在这种情况下，输出应该是：

[[(0,1),(2,3),(4,5),(6,7)], [(0,1),(2,3),(4,5),(6,3)], [(0,1),(2,3),(4,1),(6,3)]]

编辑：这是我的树的结构

class Tree:
    def __init__(self, value, d = 0):
        self.value = value
        self.children = []

    def add_child(self, child):
        self.children.append(child)

    def deep_print(self, d=0):
        if self == None:
            return
        print("   "*d, self.value)
        for child in self.children:
            child.deep_print(d + 1)

标签： pythonrecursiontree

Answer 1

遵循以下几行的递归方法应该可以工作：

def paths(self):
    if not self.children:
        return [[self.value]]  # one path: only contains self.value
    paths = []
    for child in self.children:
        for path in child.paths():
            paths.append([self.value] + path)
    return paths