Hello 👋
Cette semaine on se retrouve pour un problème d’arbre binaire, le 236. Lowest Common Ancestor of a Binary Tree 🔗.
L’énoncé
Étant donné un arbre binaire
T
, trouvez l'ancêtre commun le plus bas pour deux nœuds de l'arbre.La définition est la suivante : « L'ancêtre commun le plus bas entre deux nœuds
p
etq
est défini comme le nœud le plus bas deT
qui a à la foisp
etq
comme descendants. Un noeud peut être son propre ancêtre le plus bas."
Piste de résolution
Nous avons donc un arbre. Commençons par le traverser, puis nous regarderons comment storer de l’information dans des variables intermédiaires pour répondre au problème.
💡 Il y a plusieurs manières de parcourir un arbre. Ici, nous utilisons la DFS et faisons une traversée dite “en ordre”. C’est à dire que pour un noeud donné, son descendant gauche et son descendant droit, nous traversons de gauche à droite:
Voici une fonction itérative utilisant une stack qui traverse un arbre en ordre:
def dfs(root: TreeNode) -> TreeNode: | |
stack = [] | |
while root or stack: | |
while root: | |
stack.append(root) | |
root = root.left | |
root = stack.pop() | |
print('Processing {}'.format(root.val)) | |
root = root.right |
Voici l’algorithme ci-dessus en action:
Notez bien l’ordre dans lequel on processe les noeuds: on ne les processe pas forcément la première fois qu’on les rencontre!
La stack permet de savoir où continuer si on explore une branche en entier.
🏆 La solution
En regardant l’algorithme ci-dessus, quelles sont les modifications à faire pour résoudre le problème donné?
On doit garder trace, avec l’aide d’une variable, lorsqu’on rencontre
p
et q dans l’arbreT
. On peut en effet intuiter que l’algorithme s’arrêtera dès que l’on aura vup
etq
. Commep
etq
sont inter-changeables, on utilise un simple compteur, que l’on appellefound
, que l’on incrémente de 1 lorsqu’on rencontrep
ouq
pour la première fois. On pourra alors utiliser les conditionsif found == 1
, puisif found == 2
pour arrêter l’algorithme.Cependant, nous avons plusieurs noeuds dans T et la valeur de
found
peut être différente pour chaque noeud. Cela est lié à la stack. En effet, regardez l’example ci-dessus, avec p = 5 et q = 1:
- Lorsque l’on push le noeud 3 dans la stack,found
sera égal à 0, car c’est le premier noeud et nous n’avons pas encore vup
ouq
. Standard stuff.
- Lorsque nous processons 5 (avant de processer 3, qui est encore dans la stack),found
passe à 1.
- Lorsque l’on dépile 3 de la stack,found
reste à 1 mais on doit prendre en compte le fait que l’on qu’on a mis 3 dans la stack, nous n’avions pas encore vu p ou q, etfound
était alors à 0.
💡 En effet, la différence entre la valeur actuelle de found et la valeur lorsqu’on met un noeud dans la stack indique que ce noeud est au-dessus du précédent. C’est donc possiblement son ancêtre.On va donc stocker la valeur de found avec chaque noeud. En Python, rien de plus simple: on push des tuples dans la stack.
On doit aussi garder trace de l’ancêtre (qui est le noeud que l’on retourne à la fin).
Voici le code permettant de faire cela:
def lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode: | |
def dfs(root: TreeNode) -> TreeNode: | |
stack, found, ancestor = [], 0, None | |
while root or stack: | |
while root: | |
stack.append((root, found)) | |
root = root.left | |
root, had_already_found_one = stack.pop() | |
found += root in [p,q] | |
if found == 2: | |
return ancestor if had_already_found_one else root | |
elif not had_already_found_one and found == 1: | |
ancestor = root | |
root = root.right | |
return dfs(root) |
Et une illustration de cet algorithme:
🔎 Les lignes 15 - 18 en détail:
if found == 2
: La condition d’arrêt final de notre algorithme. On retourneancestor
si le noeud que l’on est en train de processer est le 2ème dep
ouq
. Sinon, cela veut dire que ce noeud (disonsp
) aq
pour descendant:p
est ainsi son propre ancêtre le plus bas, et aussi celui deq
par logique. On retourne alorsp
.elif not had_already_found_one and found == 1
: Cela est le cas quand on processe 3 après avoir processé 5. found est toujours égal à 1, mais lorsque nous avons mis 3 dans la stack, found était à 0. Nous n’avions ainsi pas encore vu p ou q à ce moment. Concrètement,had_already_found_one == 0
indique que l’on remonte dans l’arbre par rapport au premier noeud. On doit ainsi mettre à jourancestor
.
Voici le résumé de la session 👇
Voilà pour cette semaine! On continue avec les arbres la semaine prochaine: On s’attaquera au 297. Serialize & Deserialize a Binary Tree.