Lowest Common Ancestor of a BST
On vous donne un arbre binaire de recherche stocké selon l’ordre du tas dans le tableau tree : la racine se trouve à l’indice 0, les enfants de l’indice i se trouvent aux indices 2*i+1 (à gauche) et 2*i+2 (à droite), et -1 indique un emplacement vide. Chaque valeur du sous-arbre gauche d’un nœud est inférieure à la valeur de ce nœud, et chaque valeur de son sous-arbre droit est supérieure.
Écrivez lowestCommonAncestor, qui renvoie la valeur du plus bas ancêtre commun des valeurs p et q, toutes deux présentes dans l’arbre : le nœud le plus profond qui les a toutes deux dans son sous-arbre. Un nœud fait partie de son propre sous-arbre ; ainsi, si p se trouve au-dessus de q, la réponse est p.
Fonction
- treeinteger-array
- l’arbre binaire de recherche en parcours par niveaux, avec -1 pour un emplacement vide
- pinteger
- la première valeur à trouver
- qinteger
- la deuxième valeur à trouver
- Renvoieinteger
- la valeur du nœud le plus profond qui a à la fois p et q dans son sous-arbre
Contraintes
1 ≤ tree.length ≤ 32767- Chaque
tree[i]est égal à-1ou à une valeur telle que0 ≤ tree[i] ≤ 105. tree[0]n’est jamais-1, donc l’arbre a au moins un nœud.- Le tableau peut se terminer par des entrées
-1supplémentaires après le dernier nœud. - Les deux enfants d’un emplacement vide sont également vides, et la profondeur est d’au plus
14. - L’arbre est un arbre binaire de recherche valide, donc toutes ses valeurs sont distinctes.
petqsont des valeurs de nœuds de l’arbre. Ils peuvent être dans n’importe quel ordre et peuvent être égaux.
Exemples
- Entrée
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
- Sortie
- 8
- Explication
- En remontant depuis
3et depuis15, le premier nœud qu’ils atteignent tous les deux est8:3est son enfant gauche et15se trouve sous12, à sa droite. La racine20est également un ancêtre commun, mais plus haut.
- Entrée
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
- Sortie
- 12
- Explication
10est l’enfant gauche de12, et un nœud compte comme son propre ancêtre ;12contient donc les deux valeurs, et aucun nœud en dessous ne les contient. Ici,pest la plus grande valeur.
- Entrée
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- Sortie
- 70
- Explication
- Les deux valeurs sont supérieures à la racine
50, elles se trouvent donc toutes les deux à sa droite. À70, elles se séparent :55est plus petite et se trouve à gauche, sous60, et80est plus grande.
Pour aller plus loin
Que changerais-tu si p ou q pouvait manquer dans l’arbre et que la fonction devait renvoyer -1 dans ce cas ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Placez-vous à la racine. Si
petqsont tous deux plus petits que sa valeur, dans quel sous-arbre se trouvent-ils tous les deux ?Tant que les deux valeurs se trouvent du même côté du nœud actuel, tous les ancêtres communs situés plus bas se trouvent également de ce côté. Le premier nœud où elles ne se trouvent pas du même côté, ou qui contient l’une d’elles, est celui que tu cherches.
Commence à l’indice
0. Tant que les deux valeurs sont inférieures àtree[i], passe à2*i+1; tant qu’elles sont toutes les deux supérieures, passe à2*i+2. Sinon, renvoietree[i].
Solution
Un arbre de recherche indique, à chaque nœud, où se trouve une valeur : les plus petites à gauche, les plus grandes à droite. Commence au nœud racine et avance du côté qui contient les deux valeurs. Le premier nœud où elles cessent de partager le même côté est la réponse, et tu l’atteins en suivant un seul chemin.
Rechercher dans tout l’arbre, sans tenir compte de l’ordre
Intuition
Cette méthode fonctionne sur n’importe quel arbre binaire. Un find(i) récursif indique ce que contient le sous-arbre en i. Un nœud contenant p ou q se signale lui-même : si l’autre valeur se trouve en dessous de lui, il s’agit de la réponse ; sinon, un nœud situé plus haut voit les deux. Tout autre nœud interroge ses deux enfants. Si les deux signalent quelque chose, p et q se trouvent de part et d’autre, et ce nœud est celui où ils se rencontrent ; si un seul le fait, transmettez-le vers le haut.
Pour 3 et 15, le 8 reçoit l’indice 3 de son enfant gauche et l’indice 10 de son enfant droit, puis se signale lui-même. La méthode peut visiter chaque nœud : temps O(n) et O(h) pour la récursion.
Algorithme
- Écris
find(i). Si l’emplacement àiest vide (au-delà de la fin ou égal à-1), renvoie-1. - Si
tree[i]estpouq, renvoiei. - Appelle
findsur2*i+1et2*i+2. Si les deux ont trouvé quelque chose, renvoiei. - Sinon, renvoie le côté qui a trouvé quelque chose, ou
-1. - Renvoie
tree[find(0)].
def lowestCommonAncestor(tree, p, q):
n = len(tree)
def find(i):
# In the subtree at index i: the index of the answer if both values are
# inside, the index of the one that is, or -1 when neither is.
if i >= n or tree[i] == -1:
return -1
if tree[i] == p or tree[i] == q:
return i
left = find(2 * i + 1)
right = find(2 * i + 2)
if left != -1 and right != -1:
return i # one value on each side: this node is the answer
return left if left != -1 else right
return tree[find(0)]Comparez les deux chemins de recherche
Intuition
Recherchez une valeur de la manière habituelle : à partir de la racine, allez à gauche si elle est plus petite que le nœud et à droite si elle est plus grande. Le chemin de la racine à un nœud est unique ; le parcours passe donc par tous les ancêtres de la valeur et rien d’autre.
Notez les deux parcours. Ils partagent des nœuds jusqu’à ce que les valeurs prennent des chemins différents ; leur début commun liste donc les ancêtres communs, et sa dernière valeur est le plus bas. Pour 3 et 15, les chemins sont 20, 8, 3 et 20, 8, 12, 15 : ils partagent 20, 8, donc la réponse est 8. Chaque parcours effectue un pas par niveau : temps O(h) et espace O(h) pour les listes.
Algorithme
- Écrivez
path(target): commencez à l’indice0, enregistreztree[i], arrêtez-vous lorsqu’il est égal àtarget, sinon passez à2*i+1sitargetest plus petit et à2*i+2s’il est plus grand. - Construisez le chemin vers
pet le chemin versq. - Parcourez les deux listes depuis le début et renvoyez la dernière valeur qu’elles ont en commun.
def lowestCommonAncestor(tree, p, q):
def path(target):
# The values met on the way from the root down to target.
values = []
i = 0
while True:
values.append(tree[i])
if tree[i] == target:
return values
i = 2 * i + 1 if target < tree[i] else 2 * i + 2
to_p, to_q = path(p), path(q)
# Both paths start at the root; the answer is the last value they share.
answer = to_p[0]
for a, b in zip(to_p, to_q):
if a != b:
break
answer = a
return answerDescendez jusqu’à ce que les valeurs se séparent
Intuition
Les deux chemins coïncident tant que p et q avancent dans la même direction : parcours-les donc simultanément. À un nœud contenant v, si les deux valeurs sont plus petites, elles se trouvent toutes deux dans le sous-arbre gauche, tout comme chaque ancêtre commun situé plus bas que v : va à gauche. Si les deux sont plus grandes, va à droite.
Sinon, l’une des valeurs est plus petite et l’autre plus grande : aucun enfant de v ne contient les deux, ou bien l’une d’elles est égale à v, qui est son propre ancêtre. Dans les deux cas, v est le nœud le plus profond situé au-dessus des deux. Dans le troisième exemple, 50 est inférieur aux deux valeurs, donc va à droite jusqu’à 70, où 55 est plus petit et 80 plus grand. Une paire de comparaisons par niveau donne un temps en O(h) et un espace en O(1).
Algorithme
- Commencez à l’indice
i = 0. - Lisez
v = tree[i]. - Si
p < vetq < v, passez à2*i+1et recommencez. - Si
p > vetq > v, passez à2*i+2et recommencez. - Sinon, renvoyez
v.
def lowestCommonAncestor(tree, p, q):
i = 0 # start at the root
while True:
value = tree[i]
if p < value and q < value:
i = 2 * i + 1 # both are smaller: the answer is on the left
elif p > value and q > value:
i = 2 * i + 2 # both are larger: the answer is on the right
else:
return value # they split here, or one of them is this node
Pièges et cas limites
- Utiliser
≤et≥dans les tests de déplacement. Avecp = 12etq = 10, le parcours dépasse12pour aller à10, puis retourne10ou sort de l’arbre. - Supposer que
p < q. Dans le deuxième exemple,pest la valeur la plus grande. Comparer les deux à la valeur du nœud, ou les échanger d’abord. - Retourner l’indice au lieu de la valeur. La réponse est
tree[i], pasi. - En Lua et en R, les tableaux commencent à 1. Garder les indices des nœuds à partir de 0 pour le calcul
2*i+1et liretree[i + 1].
Questions fréquentes3
Quelle est la complexité temporelle de l’ancêtre commun le plus bas dans un BST ?
Le parcours depuis la racine suit un seul chemin, il prend donc un temps O(h) pour un arbre de profondeur h et un espace supplémentaire O(1). Pour un arbre équilibré, cela correspond à O(log n) ; pour un arbre en forme de chemin unique, cela correspond à O(n).
En quoi le LCA dans un arbre binaire de recherche diffère-t-il du LCA dans un arbre binaire ?
Dans un arbre binaire ordinaire, une valeur peut se trouver n’importe où, donc il se peut que tu doives rechercher dans chaque nœud, ce qui représente un travail en O(n). Dans un arbre de recherche, comparer les deux valeurs à celle d’un nœud t’indique de quel côté se trouve chacune, donc tu suis un seul chemin depuis la racine.
Un nœud peut-il être son propre plus bas ancêtre commun ?
Oui. Un nœud est considéré comme un ancêtre de lui-même : ainsi, lorsque p se trouve au-dessus de q, la réponse est p, et lorsque les deux valeurs sont égales, la réponse est cette valeur.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
def lowestCommonAncestor(tree, p, q):
# Écrivez le code iciTest #1
Test #2
Test #3
Arguments
tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] p = 3 q = 15
Résultat attendu
8