Lowest Common Ancestor

Donat un BST a (no buit, que conté nombres enters com a elements, i tots
són diferents) i dos nombres enters p i q tal que:

- són elements d’a

- són diferents

volem trobar el Lowest Common Ancestor (LCA, en català seria el “node
més baix comú”) de p i q dins l’arbre a.

L’LCA de p i q, respecte d’a, es defineix com el node més baix de
l’arbre a que té tant p com q com a descendents. Cal tenir en compte que
un node es pot considerar descendent de sí mateix, és a dir, si un dels
nodes p o q és un avantpassat de l’altre, aleshores aquest node
avantpassat seria el LCA.

Escriviu dues funcions que calculin l’LCA de p i q, respecte d’a. Una
d’elles (lca_recur(a,p,q)) ho farà recursivament i l’altre
(lca_iter(a,p,q)) iterativament.

Paràmetres i retorn de la funció demanada

Els paràmetres de les dues funcions són: un arbre a que és un BST no
buit amb nombres enters, tots diferents, com a elements, dos enters
diferents p i q, que són elements del BST a.

El retorn de totes dues funcions és un nombre enter.

Entrada

L’entrada al programa serà: un nombre n i una llista d’n nombres enters
diferents amb els que construirem el BST.

Després venen dos nombres enters diferents (tots dos han d’estar en la
llista amb la que acabem de construir el BST).

Vegeu els exemples del joc de proves públic.

Sortida

La sortida han de ser dos nombres enters, separats per un espai. Tots
dos haurien de ser iguals. Un d’ells és l’LCA de l’entrada calculat
recursivament, i l’altre és l’LCA de l’entrada calculat iterativament
(vegeu el programa principal a code.py).

Vegeu els exemples del joc de proves públic.

Observacions

Heu de baixar-vos el fitxer code.py (icona de la serp). Aquest fitxer és
un programa amb tot el que cal per executar els jocs de prova públics.
Només falta, clar, les funcions que us demana l’enunciat. Aquest fitxer
l’heu de completar amb el codi que falta, i això, tot, és el que heu
d’enviar al Jutge com a solució.

Dins el fitxer code.py teniu la classe BST que hem treballat a les
classes de l’assignatura. Ha estat modificada per fer més senzilla la
solució del problema (vegeu els comentaris a code.py). No caldrà que la
vostra solució faci cap import ni res. Tot el codi que us cal el teniu
dins de code.py.

L’eficiència i la qualitat de la solució es tindran en compte a la
correcció manual.

Informació del problema

Autoria: Jordi Delgado

Generació: 2026-06-10T17:03:17.574Z

© Jutge.org, 2006–2026.
https://jutge.org
