Bottom View of Binary Tree

Q: Quelle est la complexité temporelle de la vue du bas d’un arbre binaire ?

O(n) pour n nœuds : la recherche en largeur traite chaque nœud une fois et effectue une écriture dans la table de hachage. Une map ordonnée, comme une map basée sur un arbre, ajoute un facteur log w pour w colonnes.

MoyenParcours d’arbre Hachage

+10

Le tableau root contient un arbre binaire : la racine à l’indice 0, les enfants de l’indice i aux indices 2i+1 (à gauche) et 2i+2 (à droite), -1 pour un emplacement vide, et éventuellement des entrées -1 supplémentaires à la fin.

La racine se trouve dans la colonne 0 ; un déplacement vers la gauche fait reculer d’une colonne, un déplacement vers la droite fait avancer d’une colonne. Vu d’en bas, chaque colonne montre son nœud le plus profond et, en cas d’égalité, le dernier sur ce niveau lorsqu’on lit de gauche à droite (l’indice le plus grand). Renvoie les valeurs que tu vois, en commençant par la colonne la plus à gauche.

Fonction

bottomView(root: integer-array) → integer-array

rootinteger-array: l’arbre dans l’ordre du tas, avec -1 pour un emplacement vide
Renvoieinteger-array: la valeur vue depuis le bas dans chaque colonne, en commençant par la colonne la plus à gauche

Contraintes

1 ≤ root.length ≤ 32767
Chaque root[i] est -1 ou une valeur telle que 0 ≤ root[i] ≤ 10⁴, et aucune valeur n'apparaît deux fois.
root[0] n'est jamais -1, donc l'arbre contient au moins un nœud.
L’array 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 l’arbre comporte au plus 14 niveaux.

Exemples

Entrée: root = [5, 2, 9, 4, 7, 1, 6]
Sortie: [4, 2, 1, 9, 6]
Explication: La colonne 0 contient 5 et, deux niveaux plus bas, 7 (index 4) et 1 (index 5). 1 apparaît plus tard au même niveau, donc c’est lui qui s’affiche. Les colonnes -2, -1, 1 et 2 contiennent 4, 2, 9 et 6.

Entrée: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Sortie: [5, 4, 3]
Explication: La colonne -1 contient 2 et, deux niveaux plus bas, 5 (indice 9), donc tu vois 5. Dans la colonne 0, 4 se trouve sous la racine. La colonne 1 ne contient que 3.

Entrée: root = [8, -1, -1, -1]
Sortie: [8]
Explication: Chaque emplacement après la racine est -1, donc 8 est le seul nœud et la colonne 0 est la seule colonne.

Pour aller plus loin

Si une égalité au niveau le plus profond d’une colonne doit renvoyer tous les nœuds ex æquo, de gauche à droite, comment faudrait-il modifier la version en parcours en largeur ? Que renverrait la colonne 0 de l’exemple 1 ?

Solution

Chaque colonne indique son nœud le plus profond, et en cas d’égalité, c’est le nœud qui vient plus tard dans l’ordre par niveau qui l’emporte. Une recherche en largeur visite les nœuds dans l’ordre par niveau ; le dernier nœud visité dans une colonne est donc la réponse : laisse chaque nœud remplacer la valeur de sa colonne.

Parcours en profondeur, nœud le plus profond par colonne

Intuition

Parcourez l’arbre en profondeur, en attribuant à chaque nœud sa colonne et sa profondeur, et conservez, pour chaque colonne, la profondeur et la valeur du nœud le plus profond rencontré jusqu’ici.

Visiter le sous-arbre gauche avant le droit permet de rencontrer les nœuds d’un niveau de gauche à droite ; le nœud recherché est donc le dernier rencontré : remplacez-le lorsque la profondeur est supérieure ou égale. Dans l’exemple 1, le parcours rencontre 7, puis 1, tous deux à la profondeur 2 dans la colonne 0, et 1 prend la place dans la colonne.

Les colonnes forment une plage continue : suivez donc la plus petite et la plus grande, puis lisez chaque colonne entre les deux. Une visite par nœud donne un temps en O(n), et la récursion atteint une profondeur de h appels pour un arbre de h niveaux.

Algorithme

Visitez la racine avec la colonne 0 et la profondeur 0.
Ignorez l’index i lorsqu’il dépasse la fin du tableau ou que root[i] vaut -1.
Si la colonne ne contient pas encore de nœud, ou si cette profondeur est supérieure ou égale à celle qui est stockée, stockez cette profondeur et cette valeur.
Visitez 2i+1 avec la colonne col-1, puis 2i+2 avec la colonne col+1, tous deux un niveau plus bas.
Renvoyez les valeurs stockées, en commençant par la colonne la plus petite.

def bottomView(root):
    n = len(root)
    best = {}  # column -> (depth, value) of the deepest node found so far

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace on a greater or equal depth: on a tie, the node
        # met last is the one further right, which comes later in level order.
        if col not in best or depth >= best[col][0]:
            best[col] = (depth, root[i])
        visit(2 * i + 1, col - 1, depth + 1)
        visit(2 * i + 2, col + 1, depth + 1)

    visit(0, 0, 0)
    # The columns that hold a node form one unbroken range.
    return [best[col][1] for col in range(min(best), max(best) + 1)]

Parcours en largeur, dernier nœud de chaque colonne

Intuition

Une file d’attente dans laquelle chaque nœud, lorsqu’il en sort, ajoute son enfant gauche, puis son enfant droit, distribue les nœuds dans l’ordre des niveaux : chaque nœud de profondeur d avant tout nœud de profondeur d+1, et chaque niveau de gauche à droite. Parmi les nœuds d’une même colonne, le plus profond sort en dernier et, en cas d’égalité, celui le plus à droite. Ainsi, lorsque chaque nœud remplace la valeur de sa colonne, chaque emplacement finit par contenir le nœud vu d’en bas, sans qu’il soit nécessaire de comparer les profondeurs.

Dans l’exemple 1, 7 écrit dans la colonne 0 et 1 le remplace.

Chaque nœud nécessite une visite dans la file d’attente et une écriture dans la map : temps O(n). La file d’attente peut contenir un niveau entier, soit environ la moitié des nœuds ; l’espace requis est donc O(n).

Algorithme

Place la paire (index 0, colonne 0) dans une file.
Retire une paire (i, col) et stocke root[i] sous col, en remplaçant toute valeur précédente.
Ajoute (2i+1, col-1), puis (2i+2, col+1), pour chaque enfant qui se trouve dans le tableau et n'est pas -1.
Répète jusqu'à ce que la file soit vide, en suivant la colonne la plus petite et la plus grande.
Retourne les valeurs de la map, en commençant par la plus petite colonne.

from collections import deque


def bottomView(root):
    n = len(root)
    bottom = {}  # column -> value of the last node seen in that column
    queue = deque([(0, 0)])  # (node index, column); the root is never empty
    while queue:
        i, col = queue.popleft()
        # The queue hands out deeper nodes later, and right after left
        # on one level, so the last node to reach a column is the one seen from below.
        bottom[col] = root[i]
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and root[left] != -1:
            queue.append((left, col - 1))
        if right < n and root[right] != -1:
            queue.append((right, col + 1))
    # The columns that hold a node form one unbroken range.
    return [bottom[col] for col in range(min(bottom), max(bottom) + 1)]

Pièges et cas limites

Ne remplacer qu’à une profondeur strictement supérieure dans la version en profondeur d’abord. Dans l’exemple 1, cela conserve 7 au lieu de 1.
Conserver le premier nœud rencontré par une recherche en largeur pour chaque colonne. C’est la vue du dessus.
Ajouter l’enfant droit à la file avant l’enfant gauche. Chaque niveau apparaît alors de droite à gauche, et les égalités sont départagées en faveur du mauvais nœud.
Prendre les feuilles comme réponse. Dans l’exemple 1, la feuille 7 est masquée par 1, et dans l’exemple 2, le nœud 4 a un enfant, mais se trouve tout en bas de la colonne 0.
Trier les colonnes comme du texte. En tant que chaînes, "-10" se retrouve entre "-1" et "-2".

Questions fréquentes3

Qu’est-ce que la vue du bas d’un arbre binaire ?

Attribue à la colonne racine la valeur 0, à chaque pas vers la gauche une colonne de moins et à chaque pas vers la droite une colonne de plus. La vue du bas répertorie le nœud le plus profond de chaque colonne, de gauche à droite. Ce problème départage les nœuds de même profondeur selon l’ordre par niveau, en conservant le nœud le plus tardif.

Quelle est la complexité temporelle de la vue du bas d’un arbre binaire ?

O(n) pour n nœuds : la recherche en largeur traite chaque nœud une fois et effectue une écriture dans la table de hachage. Une map ordonnée, comme une map basée sur un arbre, ajoute un facteur log w pour w colonnes.

Quelle est la différence entre la vue de dessus et la vue de dessous ?

Les deux sélectionnent un nœud par colonne. La vue du dessus sélectionne le nœud le moins profond et la vue du dessous, le plus profond. Dans la version en parcours en largeur, la vue du dessus conserve la première valeur reçue par une colonne ; la vue du dessous la remplace à chaque fois.

def bottomView(root):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

root = [5, 2, 9, 4, 7, 1, 6]

Résultat attendu

[4, 2, 1, 9, 6]