Vertical Order Traversal of a Binary Tree

+10

Un arbre binaire est stocké dans le tableau root selon l’ordre d’un tas : 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), -1 indique un emplacement vide, et le tableau peut se terminer par des entrées -1 supplémentaires.

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. Renvoyez une liste par colonne, de gauche à droite. Dans chaque colonne, énumérez les nœuds de haut en bas, et les nœuds partageant une colonne et une profondeur par ordre croissant de valeur.

Fonction

verticalTraversal(root: integer-array) → integer-2d-array

rootinteger-array: l’arbre en ordre de tas, avec -1 pour une place vide
Renvoieinteger-2d-array: une liste de valeurs par colonne, en commençant par la colonne la plus à gauche, de haut en bas

Contraintes

1 ≤ root.length ≤ 32767
Chaque root[i] vaut -1 ou une valeur telle que 0 ≤ root[i] ≤ 5000, et aucune valeur n'apparaît deux fois.
root[0] n'est jamais -1, donc l'arbre comporte 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 maximum 14 niveaux.

Exemples

Entrée: root = [5, 2, 9, 4, 7, 1, 6]
Sortie: [[4], [2], [5, 1, 7], [9], [6]]
Explication: La colonne 0 contient la racine 5, puis 7 et 1 deux niveaux plus bas. Ces deux nœuds partagent la même colonne et la même profondeur, donc 1 vient avant 7, même si 7 est plus à gauche.

Entrée: root = [1, 2, 3, -1, 4, -1, -1, -1, -1, 5]
Sortie: [[2, 5], [1, 4], [3]]
Explication: La colonne -1 contient 2 à la profondeur 1 et 5 à la profondeur 3 (le fils gauche de 4). La colonne 0 contient la racine 1 et 4 à l’index 4. La colonne 1 contient uniquement 3.

Entrée: root = [6, -1, -1]
Sortie: [[6]]
Explication: 6 n’a pas d’enfants, donc la réponse comporte une seule colonne, [6].

Pour aller plus loin

Chaque valeur est au plus égale à 5000. Peux-tu utiliser cette information pour éliminer le tri par comparaison et terminer en O(n + 5000) ?

Solution

Chaque nœud possède trois clés : colonne, profondeur et valeur. La réponse est constituée des nœuds triés selon ces clés, avec une liste par colonne. En cas d’égalité pour la colonne et la profondeur, on départage selon la valeur, et non selon l’ordre de gauche à droite dans lequel un parcours les rencontre ; tu dois donc effectuer un tri : soit de tous les nœuds à la fois, soit de chaque niveau d’un parcours en largeur.

Enregistrez chaque nœud, puis triez

Intuition

Visitez chaque nœud une fois, dans n’importe quel ordre, et enregistrez le triplet (colonne, profondeur, valeur). Un déplacement vers un enfant augmente la profondeur de 1 et déplace la colonne de 1 vers la gauche ou la droite. Triez ensuite les triplets par colonne, profondeur et valeur. Les nœuds de chaque colonne sont alors regroupés, dans l’ordre requis. Parcourez la liste triée et commencez une nouvelle liste interne chaque fois que la colonne change.

Dans l’exemple 1, les triplets de la colonne 0 sont triés ainsi : (0, 0, 5), (0, 2, 1), (0, 2, 7). Le tri, O(n log n), domine le parcours en O(n), et les triplets occupent un espace de O(n).

Algorithme

Empilez (index 0, colonne 0, profondeur 0).
Dépilez un nœud, enregistrez (colonne, profondeur, valeur) et empilez chaque enfant réel avec la colonne col-1 ou col+1 et la profondeur depth+1.
Lorsque la pile est vide, triez les triplets par colonne, puis par profondeur, puis par valeur.
Parcourez-les, en commençant une nouvelle liste chaque fois que la colonne change.

def verticalTraversal(root):
    n = len(root)
    entries = []  # (column, depth, value) for every node
    stack = [(0, 0, 0)]  # (node index, column, depth); the root is never empty
    while stack:
        i, col, depth = stack.pop()
        entries.append((col, depth, root[i]))
        for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
            if child < n and root[child] != -1:
                stack.append((child, child_col, depth + 1))
    # Column, then depth, then value: exactly the order of the answer.
    entries.sort()
    result = []
    for k, (col, depth, value) in enumerate(entries):
        if k == 0 or col != entries[k - 1][0]:
            result.append([])  # a new column starts
        result[-1].append(value)
    return result

Niveau par niveau, triez à l’intérieur de chaque niveau

Intuition

Un parcours en largeur traite un niveau à la fois. Si chaque nœud ajoute sa valeur à la liste de sa colonne lorsqu’il est traité, chaque liste est déjà dans l’ordre du haut vers le bas : il n’est donc pas nécessaire de trier par profondeur. Les égalités ne se produisent qu’au sein d’un même niveau ; triez donc chaque niveau par colonne, puis par valeur, avant de le traiter.

Dans l’exemple 1, le niveau 2 arrive sous la forme 4, 7, 1, 6 dans les colonnes -2, 0, 0, 2 et se retrouve trié ainsi : 4, 1, 7, 6. La colonne 0 devient donc [5, 1, 7]. Les colonnes occupées forment une plage continue ; il suffit donc de suivre la plus petite et la plus grande.

Le tri d’un niveau de m nœuds coûte O(m log m). Dans le pire des cas, la complexité reste de O(n log n), car le dernier niveau d’un arbre complet contient environ la moitié des nœuds. L’espace requis est de O(n).

Algorithme

Commence avec un niveau contenant (index 0, colonne 0).
Trie le niveau par colonne, puis par valeur.
Dans cet ordre, ajoute chaque valeur à la liste de sa colonne et collecte ses véritables enfants, avec les colonnes col-1 et col+1, dans le niveau suivant.
Répète jusqu’à ce qu’un niveau soit vide, en suivant la colonne la plus petite et la plus grande.
Renvoie les listes de la colonne la plus petite à la plus grande.

def verticalTraversal(root):
    n = len(root)
    columns = {}  # column -> its values, top to bottom
    level = [(0, 0)]  # (node index, column) of every node on the current level
    while level:
        # Every node here has the same depth: order them by column, then value.
        level.sort(key=lambda node: (node[1], root[node[0]]))
        next_level = []
        for i, col in level:
            columns.setdefault(col, []).append(root[i])
            for child, child_col in ((2 * i + 1, col - 1), (2 * i + 2, col + 1)):
                if child < n and root[child] != -1:
                    next_level.append((child, child_col))
        level = next_level
    # The columns that hold a node form one unbroken range.
    return [columns[col] for col in range(min(columns), max(columns) + 1)]

Pièges et cas limites

Laisser les égalités dans l’ordre de gauche à droite. Un parcours en largeur sans le tri par niveau donne [5, 7, 1] pour la colonne 0 de l’exemple 1, et non [5, 1, 7].
Ajouter les valeurs lors d’un parcours en profondeur sans tri. Dans [1, 2, 3, -1, 4, -1, -1, -1, -1, -1, 5], un parcours en privilégiant la gauche ajoute 5 (profondeur 3) à la colonne 1 avant 3 (profondeur 1).
Trier par colonne et par valeur, mais pas par profondeur. La colonne 0 de l’exemple 1 devient alors [1, 5, 7].
Indexer les colonnes avec des chaînes de caractères. Trié comme du texte, "-1" vient avant "-2", donc les colonnes à gauche de 0 sont dans le mauvais ordre.

Questions fréquentes3

Quelle est la complexité temporelle du parcours par ordre vertical d’un arbre binaire ?

Le tri de tous les nœuds par colonne, profondeur et valeur coûte O(n log n) et domine le parcours en O(n). Le tri niveau par niveau présente le même cas le plus défavorable, car le dernier niveau d’un arbre complet contient environ la moitié des nœuds. L’espace requis est de O(n).

Peut-on effectuer un parcours vertical ordonné sans tri ?

Seulement si, en cas d’égalité, l’ordre est de gauche à droite. Dans ce cas, une recherche en largeur qui ajoute chaque valeur à la liste de sa colonne donne la réponse en O(n). Si les égalités sont ordonnées par valeur, il faut effectuer un tri, mais uniquement au sein d’un niveau, puisque seuls les nœuds d’un même niveau peuvent être à égalité.

Quel est le lien entre le parcours dans l’ordre vertical, la vue de dessus et la vue de dessous ?

Les trois regroupent les nœuds selon les mêmes numéros de colonne. La vue du dessus conserve le nœud le moins profond de chaque colonne, et la vue du dessous, le plus profond. Le parcours en ordre vertical conserve chaque nœud et, lorsque plusieurs partagent un niveau, les ordonne selon leur valeur, tandis que les vues font leur sélection selon leur position.

def verticalTraversal(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, 1, 7], [9], [6]]