Top View of Binary Tree

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

Un parcours en largeur visite chacun des n nœuds une fois, avec une recherche dans la map en O(1) par nœud. Il s’exécute donc en O(n) si tu suis les colonnes minimale et maximale. Une map ordonnée des colonnes donne une complexité de O(n log w) pour w colonnes.

MoyenParcours d’arbre Hachage

+10

Vous obtenez un arbre binaire stocké dans le tableau root dans l’ordre d’un tas : la racine à l’index 0, les enfants de l’index i aux index 2*i+1 (à gauche) et 2*i+2 (à droite), et -1 pour un emplacement vide.

La racine se trouve dans la colonne 0 ; un enfant gauche se trouve une colonne à gauche de son parent et un enfant droit, une colonne à droite. Vue d’en haut, on voit le nœud le moins profond de chaque colonne ; en cas d’égalité, on choisit celui qui apparaît en premier dans son niveau, de gauche à droite (l’index le plus petit). Renvoyez les valeurs visibles, de la colonne la plus à gauche à la colonne la plus à droite.

Fonction

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

rootinteger-array: l’arbre en ordre de tas, avec -1 pour une place vide
Renvoieinteger-array: la valeur vue d’en haut 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 comporte au moins un nœud.
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 l’arbre compte au plus 14 niveaux.

Exemples

Entrée: root = [5, 2, 9, 4, 7, 1, 6]
Sortie: [4, 2, 5, 9, 6]
Explication: De gauche à droite, les colonnes contiennent 4 (colonne -2), 2 (-1), la racine 5 (0), 9 (1) et 6 (2). 7 et 1 se trouvent également dans la colonne 0, mais la racine est au-dessus d’eux.

Entrée: root = [1, 2, -1, -1, 3, -1, -1, -1, -1, -1, 4]
Sortie: [2, 1, 4]
Explication: 2 se trouve dans la colonne -1. Son enfant droit 3, à l’index 4, revient dans la colonne 0, sous la racine, et est donc masqué. 4, à l’index 10, l’enfant droit de 3, est seul dans la colonne 1.

Entrée: root = [6, -1, -1]
Sortie: [6]
Explication: Les index 1 et 2 contiennent -1, donc 6 se trouve seul dans la colonne 0 et constitue toute la vue.

Pour aller plus loin

Avec des objets de nœud au lieu d’un tableau, il n’y a pas d’index pour départager une égalité. Comment formulerais-tu la règle en cas d’égalité, et ton code de parcours en largeur change-t-il ?

Solution

Chaque colonne montre son nœud le moins profond et, en cas d’égalité, celui qui apparaît en premier dans l’ordre par niveau. C’est exactement l’ordre dans lequel une recherche en largeur visite les nœuds : le premier nœud rencontré par la recherche dans une colonne est donc la réponse. Un parcours en profondeur fonctionne aussi, mais il doit suivre les profondeurs et départager les égalités avec soin.

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

Intuition

Parcours l’arbre en profondeur en notant la colonne et la profondeur de chaque nœud, et conserve, pour chaque colonne, la profondeur et la valeur du nœud le moins profond trouvé jusque-là.

Ne remplace que si la profondeur est strictement inférieure. Parmi deux nœuds à égalité, celui qui apparaît en premier dans l’ordre par niveau est atteint en premier par un parcours qui explore chaque sous-arbre gauche avant le sous-arbre droit correspondant, car il part à gauche à l’endroit où les deux chemins divergent. Remplacer à profondeur égale fait gagner le nœud rencontré plus tard : avec l’index 3 vide et des nœuds aux index 19 et 23, les deux se trouvent dans la colonne -2 à la profondeur 4, et la réponse est le nœud à l’index 19.

Les colonnes occupées forment une plage continue, car un nœud dans la colonne -3 a des ancêtres dans les colonnes -1 et -2. Il faut donc suivre la colonne la plus petite et la plus grande. Chaque nœud est visité une fois, soit un temps de O(n), et la récursion a une profondeur d’environ h appels.

Algorithme

Visitez la racine avec la colonne 0 et la profondeur 0. Revenez immédiatement si l’index est hors du tableau ou contient -1.
Si la colonne ne contient pas encore de nœud, ou si cette profondeur est strictement inférieure à celle enregistrée, enregistrez cette profondeur et cette valeur.
Visitez 2i+1 avec la colonne col-1, puis 2i+2 avec la colonne col+1, un niveau plus bas.
Renvoyez les valeurs enregistrées de la colonne la plus petite à la plus grande.

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

    def visit(i, col, depth):
        if i >= n or root[i] == -1:
            return
        # Replace only on a strictly smaller depth: on a tie, the node
        # met first is the one further left, which comes first 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, premier nœud par colonne

Intuition

Une file qui prend la racine, puis l’enfant gauche de chaque nœud et ensuite son enfant droit, libère 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. C’est la priorité du problème : le premier nœud reçu par une colonne est celui que l’on voit d’en haut, et tous les suivants sont ignorés.

Chaque nœud nécessite une recherche dans la map, soit O(n) au total. La file peut contenir un niveau entier, jusqu’à environ la moitié des nœuds ; l’espace utilisé est donc de O(n).

Algorithme

Place la paire (index 0, colonne 0) dans une file d’attente.
Retire une paire (i, col). Si la map ne contient aucune entrée pour col, stocke root[i] à cet emplacement.
Ajoute (2i+1, col-1), puis (2i+2, col+1), pour chaque enfant existant.
Lorsque la file d’attente est vide, renvoie les valeurs de la map, de la colonne la plus petite à la plus grande.

from collections import deque


def topView(root):
    n = len(root)
    top = {}  # column -> value of the first 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 shallower nodes first, and left before right
        # on one level, so the first node of a column is the one seen from above.
        if col not in top:
            top[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 [top[col] for col in range(min(top), max(top) + 1)]

Pièges et cas limites

Conserver le premier nœud rencontré lors d’un parcours en profondeur. Si l’enfant gauche de la racine a un enfant droit qui a lui-même un enfant droit (colonne 1, profondeur 3), le parcours le rencontre avant l’enfant droit de la racine (colonne 1, profondeur 1).
Mettre l’enfant droit en premier dans la file d’attente : en cas d’égalité, le mauvais nœud est choisi.
Trier les colonnes comme du texte : "-1" est trié avant "-2".
Supposer que le sous-arbre gauche occupe les colonnes négatives. Dans l’exemple 2, le nœud 4 se trouve dans le sous-arbre gauche de la racine et dans la colonne 1.

Questions fréquentes3

Qu’est-ce que la vue de dessus d’un arbre binaire ?

Numérotez les colonnes à partir de la racine en commençant à 0, en décrémentant de un pour un enfant gauche et en incrémentant de un pour un enfant droit. La vue de dessus répertorie, pour chaque colonne de gauche à droite, le nœud le plus proche de la racine.

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

Un parcours en largeur visite chacun des n nœuds une fois, avec une recherche dans la map en O(1) par nœud. Il s’exécute donc en O(n) si tu suis les colonnes minimale et maximale. Une map ordonnée des colonnes donne une complexité de O(n log w) pour w colonnes.

En quoi la vue de dessus diffère-t-elle de la vue de gauche et de la vue de dessous ?

La vue de gauche sélectionne le premier nœud de chaque niveau. La vue de dessus sélectionne le nœud le moins profond de chaque colonne. La vue de dessous sélectionne le nœud le plus profond par colonne ; une recherche en largeur pour l’obtenir remplace donc chaque colonne au lieu de conserver le premier nœud.

def topView(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, 5, 9, 6]