Lowest Common Ancestor of a BST
On vous donne un arbre binaire de recherche stocké dans le tableau tree en ordre par niveaux, ainsi que deux valeurs p et q qui y figurent toutes les deux. La racine se trouve à l’indice 0, les enfants du nœud à l’indice i se trouvent aux indices 2*i+1 (à gauche) et 2*i+2 (à droite), -1 indique une case vide, et le tableau peut se terminer par des entrées -1 supplémentaires. Dans un arbre binaire de recherche, 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 lui est supérieure.
Écrivez une fonction nommée lowestCommonAncestor qui renvoie la valeur du plus bas ancêtre commun de p et q : le nœud le plus profond qui les a tous les deux dans son sous-arbre. Un nœud est considéré comme faisant partie de son propre sous-arbre ; ainsi, si p se trouve au-dessus de q, la réponse est p lui-même.
Fonction
- treeinteger-array
- l’arbre binaire de recherche en parcours par niveaux, avec -1 pour une position 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]vaut-1ou une valeur telle que0 ≤ tree[i] ≤ 105. tree[0]n’est jamais-1, donc l’arbre comporte 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
3est le fils gauche de8, et15se trouve sous12, à droite de8. En remontant depuis chacun d’eux, le premier nœud qu’ils atteignent tous les deux est8: c’est donc la réponse ; 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. Un nœud compte comme son propre ancêtre, donc12contient les deux valeurs dans son sous-arbre et aucun nœud en dessous ne les contient : la réponse est12. Les valeurs peuvent apparaître dans n’importe quel ordre ; ici,pest la plus grande.
- Entrée
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- Sortie
- 70
- Explication
55et80sont tous deux supérieurs à la racine50, ils se trouvent donc tous deux à sa droite. Au niveau de70, ils se séparent :55est plus petit et se trouve à gauche (sous60), tandis que80est plus grand et se trouve à droite. La réponse est donc70.
+12 tests cachés à la soumission
Pour aller plus loin
Que changerais-tu si p ou q pouvait être absent de 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.
Place-toi à la racine. Si
petqsont tous deux inférieurs à sa valeur, dans quel sous-arbre se trouvent-ils ?Tant que les deux valeurs se trouvent du même côté du nœud actuel, chaque ancêtre commun situé plus bas se trouve é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 recherches.
Commencez à l’indice
0. Tant que les deux valeurs sont inférieures àtree[i], passez à2*i+1; tant que les deux sont supérieures, passez à2*i+2. Sinon, renvoyeztree[i].
Solution
Dans un arbre binaire ordinaire, vous ne pouvez pas savoir où se trouve une valeur sans rechercher des deux côtés de chaque nœud. Un arbre de recherche vous indique à chaque nœud : les valeurs plus petites sont à gauche, les plus grandes à droite. Partez donc de la racine et avancez vers le côté qui contient les deux valeurs. Le premier nœud où elles ne se trouvent plus du même côté est la réponse ; vous le trouvez en suivant un seul chemin, sans jamais regarder le reste de l’arbre.
Parcourir tout l’arbre sans tenir compte de l’ordre
Intuition
Tout d’abord, voyons comment se déplacer dans le tableau. Le nœud à l’indice i a son enfant gauche à l’indice 2*i+1 et son enfant droit à l’indice 2*i+2. Un enfant n’existe que si son indice se trouve dans le tableau et que la valeur à cet emplacement n’est pas -1. Dans [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15], la racine 20 a 8 et 31 aux indices 1 et 2, et le 12 à l’indice 4 a 10 et 15 aux indices 9 et 10.
Cette première méthode fonctionne sur n’importe quel arbre binaire. Une fonction récursive find(i) indique ce que contient le sous-arbre à l’indice i. Un emplacement vide renvoie -1. Un nœud contenant p ou q se renvoie lui-même : soit l’autre valeur se trouve en dessous, et le nœud est alors la réponse, soit l’autre valeur se trouve ailleurs, et un nœud situé plus haut trouvera les deux. Sinon, le nœud interroge ses deux enfants. Si les deux côtés renvoient une valeur, p se trouve d’un côté et q de l’autre : c’est donc à ce nœud qu’ils se rejoignent. Si un seul côté renvoie une valeur, on la transmet vers le haut.
Pour p = 3 et q = 15, le 8 reçoit l’indice 3 de son enfant gauche et l’indice 10 de son enfant droit ; il se renvoie donc lui-même. La racine reçoit cette valeur de son enfant gauche et -1 de son enfant droit, puis transmet le 8 vers le haut.
La méthode est correcte, mais elle peut visiter tous les nœuds : elle s’exécute en O(n), avec une complexité de O(h) pour la récursion. Elle n’utilise jamais l’ordre des valeurs, qui est pourtant tout l’intérêt d’un arbre de recherche.
Algorithme
- Écris
find(i). Si l’emplacement àiest vide (au-delà de la fin ou-1), retourne-1. - Si
tree[i]estpouq, retournei. - Appelle
findsur2*i+1et2*i+2. Si les deux ont trouvé quelque chose, retournei. - Sinon, retourne le côté qui a trouvé quelque chose, ou
-1. - Retourne
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
Utilisez maintenant l’ordre. Vous pouvez trouver une valeur comme un arbre de recherche est conçu pour être parcouru : commencez à la racine, allez à gauche lorsque la valeur est inférieure à celle du nœud, à droite lorsqu’elle est supérieure, et arrêtez-vous lorsque vous l’atteignez. Ce parcours passe par tous les ancêtres de la valeur et rien d’autre, car le chemin de la racine à un nœud est unique.
Notez le parcours de p et celui de q. Les deux commencent à la racine et suivent les mêmes nœuds jusqu’à ce que les valeurs prennent des chemins différents. Leur début commun est la liste de leurs ancêtres communs ; la dernière valeur partagée est donc la plus basse. Pour 3 et 15, les chemins sont 20, 8, 3 et 20, 8, 12, 15 : ils partagent 20, 8, et la réponse est 8. Pour 12 et 10, les chemins sont 20, 8, 12 et 20, 8, 12, 10, et la réponse est 12.
Chaque parcours prend une étape par niveau ; le temps d’exécution est donc de O(h), soit au plus 14 étapes ici, quel que soit le nombre de nœuds de l’arbre. Les deux listes occupent un espace de O(h).
Algorithme
- Écrivez
path(target): commencez à l’indice0, enregistreztree[i], arrêtez-vous lorsqu’il est égal àtarget, sinon déplacez-vous vers2*i+1sitargetest plus petit et vers2*i+2s’il est plus grand. - Construisez le chemin vers
pet le chemin versq. - Parcourez les deux listes depuis le début tant que leurs valeurs correspondent, en mémorisant la dernière correspondance.
- Renvoyez cette dernière valeur commune.
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 concordent tant que p et q avancent dans la même direction ; vous n’avez donc pas besoin de les mémoriser. Parcourez-les simultanément. À un nœud contenant v, si les deux valeurs sont inférieures à v, elles se trouvent toutes les deux dans le sous-arbre gauche, tout comme chaque ancêtre commun sous v : allez à gauche. Si elles sont toutes les deux supérieures, allez à droite.
Sinon, vous êtes arrivé. Soit une valeur est inférieure à v et l’autre est supérieure, elles se trouvent donc dans des sous-arbres différents et aucun enfant de v ne contient les deux ; soit l’une d’elles est égale à v, et un nœud 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, la racine 50 est inférieure à 55 et à 80, vous allez donc à droite jusqu’à 70. Là, 55 est inférieur et 80 est supérieur : la réponse est 70. Dans le deuxième exemple, vous allez de 20 à 8, puis à 12, qui est égal à p, et vous vous arrêtez.
Vous suivez un seul chemin depuis la racine, avec une paire de comparaisons par niveau ; le temps d’exécution est donc O(h) et l’espace utilisé est O(1). Le reste de l’arbre n’est jamais parcouru.
Algorithme
- Commence à l’indice
i = 0. - Lis
v = tree[i]. - Si
p < vetq < v, passe à2*i+1et recommence. - Si
p > vetq > v, passe à2*i+2et recommence. - Sinon, retourne
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
Le parcours est court, donc la plupart des bugs viennent de la condition d’arrêt.
- Utiliser
≤et≥dans les tests de déplacement. Avecp = 12etq = 10, le testp ≤ 12etq ≤ 12dépasse la réponse et atteint10; à partir de là, le parcours renvoie10ou sort de l’arbre. Ne se déplacer que lorsque les deux valeurs sont strictement du même côté. - Supposer que
p < q. Les valeurs peuvent être dans n’importe quel ordre. Comparez-les toutes les deux au nœud, ou échangez-les d’abord pour quepsoit la plus petite. - Oublier qu’une valeur peut être l’ancêtre de l’autre. Dans ce cas, la réponse est cette valeur elle-même, et non son parent.
- Renvoyer l’indice au lieu de la valeur. La fonction renvoie
tree[i], et noni. - Parcourir tout l’arbre. Cela donne la bonne réponse, mais visite jusqu’à chaque nœud alors qu’un seul chemin suffit.
- Se tromper dans le décalage en Lua et en R, où les tableaux commencent à 1. Gardez les indices des nœuds à partir de 0 pour le calcul
2*i+1, et liseztree[i + 1].
Questions fréquentes4
Quelle est la complexité temporelle du plus proche ancêtre commun dans un BST ?
Le parcours depuis la racine suit un seul chemin ; il prend donc un temps de O(h) pour un arbre de profondeur h et utilise un espace supplémentaire de O(1). Pour un arbre équilibré, cela donne O(log n) ; pour un arbre en forme de chemin unique, cela donne 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ù : tu recherches donc dans les deux sous-arbres de chaque nœud, et le travail est de 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 d’elles, donc tu suis un seul chemin depuis la racine. La méthode récursive pour un arbre quelconque fonctionne aussi sur un arbre de recherche, mais elle écarte cette information.
Un nœud peut-il être son propre plus proche ancêtre commun ?
Oui. Un nœud est considéré comme un ancêtre de lui-même, donc lorsque p se trouve au-dessus de q, la réponse est p. La même règle donne p lorsque les deux valeurs sont égales. Le parcours gère les deux cas : il s’arrête dès que le nœud courant est égal à l’une des valeurs.
Pourquoi le parcours s’arrête-t-il au premier nœud où p et q se séparent ?
À ce nœud, une valeur est plus petite et l’autre plus grande, donc elles se trouvent dans des sous-arbres différents. Tout nœud en dessous se trouve dans un seul de ces sous-arbres et ne peut pas contenir les deux. Le nœud de séparation contient les deux, et aucun nœud plus profond ne le fait ; c’est exactement la définition du plus bas ancêtre commun.
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.
Python
def lowestCommonAncestor(tree, p, q):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] p = 3 q = 15
Attendu
8