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" должен быть возвращен в каждом листе ...

is_leaf () - true, если self.children пусто.

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