Python(产量): all paths from leaves to root in a tree

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”应该在每片叶子中返回......

如果 self.children 为空，则 is_leaf() 为真。

Answer 1

这段代码只产生作为根的(直接)子节点的叶子。其他的被访问，它们屈服于上层函数，但上层函数对它们没有任何作用。您需要的是将它们从较低的函数生成到较高的函数:

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

这应该可以解决问题。