Lowest Common Ancestor of a Binary Tree

Q: En quoi cela diffère-t-il du plus bas ancêtre commun dans un arbre binaire de recherche ?

Dans un arbre de recherche, comparer p et q à un nœud vous indique de quel côté se trouve chacun, si bien qu’un seul chemin depuis la racine permet de trouver la réponse en O(h). Ici, une comparaison ne vous apprend rien, alors vous parcourez les sous-arbres.

Q: Peux-tu trouver le plus bas ancêtre commun à l’aide de pointeurs vers les parents ?

Oui. Dans ce tableau, le parent de l’index i est (i-1)/2 arrondi à l’entier inférieur. Déplacez le plus grand des deux index vers son parent jusqu’à ce qu’ils soient égaux ; un index plus grand n’est jamais un ancêtre d’un index plus petit. Avec des nœuds chaînés, placez les ancêtres de p dans un ensemble et remontez depuis q jusqu’au premier qui s’y trouve.

MoyenParcours d’arbre Récursivité

+10

Vous recevez un arbre binaire dans le tableau root, dans l’ordre d’un tas : la racine à l’indice 0, les enfants de l’indice i aux indices 2*i+1 (à gauche) et 2*i+2 (à droite), et -1 pour un emplacement vide. Les valeurs sont distinctes et ne suivent aucun ordre.

Retournez la valeur du plus bas ancêtre commun de p et q, les valeurs de deux nœuds différents : le nœud le plus profond dont le sous-arbre contient les deux. Un sous-arbre inclut son nœud racine ; ainsi, si q se trouve sous p, la réponse est p.

Fonction

lowestCommonAncestor(root: integer-array, p: integer, q: integer) → integer

rootinteger-array: l’arbre binaire dans l’ordre par niveaux, avec -1 pour une place vide
pinteger: la valeur d’un nœud
qinteger: la valeur d’un autre nœud
Renvoieinteger: la valeur du nœud le plus bas dont le sous-arbre contient à la fois p et q

Contraintes

2 ≤ root.length ≤ 32767
Chaque root[i] vaut -1 ou une valeur telle que 0 ≤ root[i] ≤ 10⁴.
root[0] n'est jamais -1, et l'arbre comporte au moins deux nœuds.
Le tableau peut se terminer par des entrées -1 supplémentaires après le dernier nœud.
Les deux enfants d’un emplacement vide sont également vides, et la profondeur est au plus 14.
Toutes les valeurs de l’arbre sont distinctes et ne suivent aucun ordre.
p et q sont les valeurs de deux nœuds différents de l’arbre, dans n’importe quel ordre.

Exemples

Entrée: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
Sortie: 3
Explication: 6 est le fils gauche de 3, et 9 se trouve sous 4, à droite de 3 : ils se rejoignent donc en 3. Comparer les valeurs désignerait la racine 8 : 6 est plus petit et 9 plus grand.

Entrée: root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
Sortie: 4
Explication: 7 est l’enfant gauche de 4, et le sous-arbre de 4 inclut 4 lui-même, donc la réponse est 4.

Entrée: root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
Sortie: 6
Explication: La racine 1 n’a pas de fils gauche. Son fils droit 6 a 3 à sa gauche et 0 à sa droite, les valeurs se rejoignent donc en 6.

Pour aller plus loin

Si p ou q peuvent être absents, avec -1 comme réponse, quel raccourci dans le parcours unique ne fonctionne plus, et comment terminer quand même en un seul parcours ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Aucun ordre ne vous indique de quel côté se trouve une valeur, vous devez donc chercher. Un seul parcours en post-ordre permet à chaque sous-arbre de signaler ce qu’il a trouvé, et les valeurs se rencontrent au premier nœud qui reçoit des informations des deux côtés.

Descends en inspectant chaque côté

Intuition

Descendez depuis la racine et, à chaque nœud, recherchez p et q dans le sous-arbre gauche. Les deux s’y trouvent : allez à gauche. Aucun des deux : allez à droite. Un dans chaque sous-arbre : les valeurs se séparent, et ce nœud est la réponse. Un nœud contenant p ou q est aussi la réponse, puisque l’autre valeur doit se trouver en dessous. Pour 6 et 9, la racine trouve les deux dans son sous-arbre gauche, et à 3, le seul 6 correspond uniquement à p.

Chaque étape vers le bas parcourt un sous-arbre entier, donc h niveaux coûtent O(n·h), et O(n²) dans un arbre haut et étroit sans limite de profondeur. La recherche à 8 a déjà parcouru tous les nœuds sous 3, et l’étape à 3 en parcourt certains à nouveau.

Algorithme

Écrivez contains(i, value) : false pour un emplacement vide (au-delà de la fin ou -1), true si root[i] est égal à value, sinon interrogez les deux enfants.
Commencez à i = 0. Si root[i] est p ou q, renvoyez-le.
Si le sous-arbre gauche à 2*i+1 contient les deux valeurs, déplacez-vous dans ce sous-arbre. S’il ne contient ni l’une ni l’autre, déplacez-vous vers 2*i+2.
Sinon, renvoyez root[i].

def lowestCommonAncestor(root, p, q):
    n = len(root)

    def contains(i, value):
        # Is value somewhere in the subtree at index i?
        if i >= n or root[i] == -1:
            return False
        if root[i] == value:
            return True
        return contains(2 * i + 1, value) or contains(2 * i + 2, value)

    i = 0  # p and q are always inside the subtree at i
    while True:
        if root[i] == p or root[i] == q:
            return root[i]  # one value is here, the other is below it
        left = 2 * i + 1
        p_left = contains(left, p)
        q_left = contains(left, q)
        if p_left and q_left:
            i = left  # both on the left
        elif not p_left and not q_left:
            i = 2 * i + 2  # both on the right
        else:
            return root[i]  # one on each side

Un parcours en postordre

Intuition

Fais répondre chaque sous-arbre une seule fois, en remontant depuis le bas. find(i) renvoie l’indice de la réponse si le sous-arbre à i contient les deux valeurs, l’indice de p ou de q s’il en contient une, et -1 s’il ne contient ni l’une ni l’autre.

Un nœud contenant p ou q renvoie son propre indice sans regarder plus bas. Si l’autre valeur se trouve dans son sous-arbre, ce nœud est la réponse ; sinon, un nœud plus haut reçoit une réponse des deux côtés. Tout autre nœud interroge ses deux enfants. Deux résultats signifient que les valeurs sont remontées de côtés différents et se rejoignent ici. Un seul résultat remonte sans modification, qu’il s’agisse d’une seule valeur ou de la réponse finale.

Dans le premier exemple, 3 reçoit l’indice 3 de son enfant gauche et 10 de son enfant droit, renvoie son propre indice 1, puis la racine le transmet. Chaque nœud est visité une seule fois : temps O(n), récursion O(h).

Algorithme

find(i) renvoie -1 pour un indice au-delà de la fin ou pour un -1.
Un nœud dont la valeur est p ou q renvoie i sans examiner ses descendants.
Tout autre nœud calcule left = find(2*i+1) et right = find(2*i+2). Si aucun des deux n’est -1, il renvoie i ; sinon, celui qui n’est pas -1, ou -1.
Renvoyez root[find(0)].

def lowestCommonAncestor(root, p, q):
    n = len(root)

    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 root[i] == -1:
            return -1
        if root[i] == p or root[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 root[find(0)]

Pièges et cas limites

Comparer les valeurs avec le nœud. L’arbre n’a pas d’ordre : dans le premier exemple, le parcours s’arrête à la racine 8 au lieu de 3.
Renvoyer true ou false au lieu d’un index. Le parent ne peut pas savoir si la réponse finale se trouve déjà en dessous de lui.
Lire un enfant sans vérifier la longueur. Le 9 à l’index 10 a pour index d’enfants 21 et 22, au-delà de la dernière entrée.
Renvoyer find(0), un index, au lieu de root[find(0)].
En Lua et en R, les tableaux commencent à 1 : gardez les index des nœuds basés sur 0 et lisez root[i + 1].

Questions fréquentes3

Quelle est la complexité temporelle du plus proche ancêtre commun dans un arbre binaire ?

Le parcours en post-ordre entre dans chaque nœud au plus une fois : temps O(n). La pile de récursion contient un cadre par niveau, donc l’espace est de O(log n) dans un arbre équilibré et de O(n) dans un arbre en forme de chemin.

En quoi cela diffère-t-il du plus bas ancêtre commun dans un arbre binaire de recherche ?

Dans un arbre de recherche, comparer p et q à un nœud vous indique de quel côté se trouve chacun, si bien qu’un seul chemin depuis la racine permet de trouver la réponse en O(h). Ici, une comparaison ne vous apprend rien, alors vous parcourez les sous-arbres.

Peux-tu trouver le plus bas ancêtre commun à l’aide de pointeurs vers les parents ?

Oui. Dans ce tableau, le parent de l’index i est (i-1)/2 arrondi à l’entier inférieur. Déplacez le plus grand des deux index vers son parent jusqu’à ce qu’ils soient égaux ; un index plus grand n’est jamais un ancêtre d’un index plus petit. Avec des nœuds chaînés, placez les ancêtres de p dans un ensemble et remontez depuis q jusqu’au premier qui s’y trouve.

def lowestCommonAncestor(root, p, q):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Arguments

root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]
p = 6
q = 9

Résultat attendu