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)

但它不起作用.为什么？在root用户调用时,它从上到下遍历树,在"acc"中收集节点."acc"应该在每一片叶片中归还......

如果self.children为空,则is_leaf()为true.

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

这应该可以解决问题.