Arbres - Mateixes fulles P88233


Statement
 

pdf   zip   main.py

thehtml

En un arbre binari, una fulla és un node sense cap fill.

Feu una funció que, donats dos arbres binaris de naturals, digui si tenen o no les mateixes fulles d’esquerra a dreta. Resoleu el problema utilitzant una funció que generi les fulles d’esquerra a dreta d’un arbre binari. Digueu quin és el cost asimptòtic en el cas millor i en el cas pitjor de les vostres funcions.

Observacions

  • Descarregueu-vos el fitxer code.py. El programa principal, les estructures de dades, la lectura de l’arbre i l’esquelet de les funcions ja se us dónen implementats.
  • El programa principal serveix per provar les funcions i llegeix p parells d’arbres en preordre (amb valors −1 pels arbres buits) i escriu, per a cada parell, les fulles d’esquerra a dreta dels dos arbres i si tenen o no les mateixes fulles d’esquerra a dreta.
  • Us pot anar bé fer servir la funció zip_longest d’itertools que funciona com zip però afegeix Nones si una de les dues seqüències acaba abans que l’altra.
Public test cases

  • Input

    8

3 0 7 -1 4 -1 -1 2 -1 -1 5 4 -1 -1 7 6 -1 1 -1 -1 -1
3 0 7 -1 4 -1 -1 3 -1 -1 5 4 -1 -1 7 -1 6 -1 1 -1 -1

5 5 1 -1 -1 2 -1 -1 5 3 -1 -1 4 -1 -1
6 6 1 -1 -1 2 -1 -1 6 3 -1 -1 4 -1 -1

5 5 1 -1 -1 2 -1 -1 5 3 -1 -1 4 -1 -1
5 5 5 1 -1 -1 2 -1 -1  5 -1 3 -1 -1 4 -1 -1 

1 2 1 -1 -1 2 -1 -1 5 3 -1 -1 4 -1 -1
1 2 1 -1 -1 2 -1 -1 5 3 -1 -1 -1

5 5 1 -1 -1 2 -1 -1 5 3 -1 -1 4 -1 -1
6 6 9 -1 -1 2 -1 -1 6 3 -1 -1 4 -1 -1

-1
-1

3 -1 -1
4 -1 -1

12 15 -1 -1 -1
12 -1 15 -1 -1

    Output

    4 2 4 1 , 4 3 4 1 , False
1 2 3 4 , 1 2 3 4 , True
1 2 3 4 , 1 2 3 4 , True
1 2 3 4 , 1 2 3 , False
1 2 3 4 , 9 2 3 4 , False
, , True
3 , 4 , False
15 , 15 , True
    • Information
    Author
    Jordi Petit
    Language
    Catalan
    Official solutions
    Python
    User solutions
    Python