Generador de camins en un arbre binari P96496

Statement

Donat un arbre binari d’enters, es vol generar tots els camins possibles des de l’arrel fins a les fulles (de l’esquerra cap a la dreta). Cada camí es representa com una llista d’enters corresponent als valors dels nodes que el formen.

Per a fer-ho, escriu un generador que implementi la següent capçalera:

    def genera_camins(arbre: Arbre) -> Iterator[list[int]]

on Arbre és un arbre binari definit per:

    @dataclass
    class Node:
        x: int
        fe: Arbre
        fd: Arbre

    Arbre: TypeAlias = Node | None

El programa principal i l’esquelet del programa ja es dónen implementats, descarrega’l! L’entrada consisteix en la descripció d’arbres binari en preordre, on les fulles estan indicades amb el valor $-1$ . La sortida és el conjunt de tots els camins des de l’arrel fins a alguna fulla, representats com a llistes d’enters en ordre d’esquerra a dreta i obtinguts amb el generador.

Public test cases

Input

1 2 -1 -1 3 -1 -1

Output

1 2
1 3

Input

10 20 40 -1 -1 50 -1 -1 30 -1 60 -1 -1

Output

10 20 40
10 20 50
10 30 60

Input

-1

Output

Input

1 2 3 -1 -1 4 5 -1 -1 6 -1 -1 7 8 -1 9 -1 -1 10 11 12 -1 -1 -1 13 -1 14 -1 -1

Output

1 2 3
1 2 4 5
1 2 4 6
1 7 8 9
1 7 10 11 12
1 7 10 13 14

Information

Author: Jordi Petit
Language: Catalan
Official solutions: Python
User solutions: Python