Python（yield）：树中从叶子到根的所有路径

Question

我想要生成一棵树中从每个叶子节点到根节点的所有路径。我想用生成器来实现，这样可以节省内存（因为树可能很大）。这是我的代码：

def paths(self, acc=[]):
    if self.is_leaf():
        yield [self.node]+acc

    for child in self.children:
        child.paths([self.node]+acc)

但是它不工作。为什么呢？在根节点调用时，它从上到下遍历树，把节点收集到“acc”里。“acc”应该在每个叶子节点返回...

is_leaf() 函数如果 self.children 为空，就会返回真。

Answer 1

现在这个 for 循环没有返回任何东西。它应该返回所有由递归调用生成的元素：

for child in self.children:
    for path in child.paths([self.node]+acc):
        yield path

Answer 2

这段代码只会返回根节点的直接子节点。其他的节点虽然会被访问到，但它们会交给上层的函数处理，但上层的函数对它们没有做任何事情。你需要的是从下层的函数把这些节点返回给上层的函数：

def paths(self, acc=[]):
    if self.is_leaf():
        yield [self.node]+acc

    for child in self.children:
        for leaf_path in child.paths([self.node]+acc): # these two
            yield leaf_path                            # lines do that

这样做就可以解决问题了。