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。

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

Answer 2

目前for循环不yield任何东西。它应该生成由递归调用生成的所有元素:

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