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

Quiero generar todos los caminos de cada hoja a la raíz en un árbol. Me gustaría hacer eso con los 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, recolectando nodos en “acc”. “acc” debe ser devuelto en cada hoja …

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

Este código solo produce hojas que son hijos (inmediatos) de la raíz. Los otros se visitan, ceden a la función superior, pero la función superior no hace nada con ellos. Lo que necesitas es cederlos de 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 funcionar.

Por el momento el bucle for no yield nada. En su lugar, debe producir 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