Python (rendimiento): todas las rutas desde las hojas hasta la raíz en un árbol

Question

Quiero generar todas las rutas desde cada hoja hasta la raíz en un árbol. Me gustaría hacer eso con generadores, para ahorrar memoria (el árbol puede ser grande). Aquí está mi código:

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

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

Pero no funciona. ¿Por qué? Invocado en la raíz, atraviesa el árbol de arriba a abajo, recogiendo nodos en "acc". "acc" debe devolverse en cada hoja ...

is_leaf() es verdadero si self.children está vacío.

Answer 1

Este código sólo produce hojas que son (inmediatos) hijos de la raíz. Los otros son visitados, ceden a la función superior, pero la función superior no hace nada con ellos. Lo que necesita es cederlos desde la función inferior a la superior:

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 

Esto debería hacer el truco.

Answer 2

En este momento, el for no hace yield nada. En su lugar, debe ceder todos los elementos que son generados por la llamada recursiva:

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