Ancestor comú més baix d'un arbre binari: dia 10 (Python)

Bloc

Ancestor comú més baix d'un arbre binari: dia 10 (Python)

Avui veurem un problema d’arbre. Abans d'entrar en el problema, entenem algunes característiques de l'arbre binari.



Un arbre binari és una estructura de dades on cada node pot tenir un màxim de dos fills. La part més superior d’un arbre s’anomena node d’arrel i els extrems s’anomenen fulla. Un arbre de qualsevol forma no pot tenir un cicle. Un exemple d’arbre binari és el següent.

Imatge per publicar



Exemple d’arbre binari.

236 . L'ancestre comú més baix d'un arbre binari



Donat un arbre binari, trobeu l’avantpassat comú (ACV) més baix de dos nodes donats a l’arbre.

D'acord amb la definició de LCA a la Viquipèdia : L'avantpassat comú més baix es defineix entre dos nodes p i q com el node més baix de T que té tant p com q com a descendents (on permetem un node per ser descendent de si mateix ).

Donat l'arbre binari següent: arrel = [3,5,1,6,2,0,8, nul, nul, 7,4]

Imatge per publicar

Exemple 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3.

Exemple 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Nota:

  • Tots els valors dels nodes seran únics.
  • p i q són diferents i els dos valors existiran a l'arbre binari.

Solució:

1. Mantingueu un diccionari que proporciona informació sobre el node fill i el seu node pare.

a. Utilitzeu una pila que conté nodes per visitar.

b. Utilitzeu un diccionari que contingui informació sobre el node fill i el seu node pare. Inicialitzeu-lo amb la clau com a arrel i el valor com cap, cosa que implica que l'arrel no té cap node pare.

c. Executeu el bucle fins que hi hagi elements a la pila.

jo. Pop node des de la pila.

ii. Comproveu si al node li queda cap fill secundari. Si és així, premeu el fill esquerre del node per apilar-lo i, al diccionari, mencioneu la tecla com a fill esquerre i el valor com a node actual. Realitzeu la mateixa operació si tenim el fill adequat per al node actual.

d. Un cop l'arbre es travessi completament, creeu un conjunt que mantindrà els avantpassats des del node1 fins al node arrel.

e. Travesseu des del node2 fins al node arrel i comproveu si hi ha algun node al conjunt anterior. Si trobem un node comú, retornem el valor del node.

L’algorisme es veurà com es mostra a continuació.

# 365dayschallenge #programming #coding #trees # leetcode-medium

medium.com

Ancestor comú més baix d'un arbre binari: dia 10 (Python)

Avui veurem un problema d’arbre. Abans d'entrar en el problema, entenem algunes característiques de l'arbre binari. Un arbre binari és una estructura de dades on cada node pot tenir un màxim de dos fills. La part més superior d’un arbre s’anomena node arrel i ...