Binary Tree Level Order Traversal

Q: Quelle est la complexité temporelle du parcours d’un arbre binaire par niveaux ?

Les deux solutions visitent chaque nœud une fois : un temps de O(n) pour n nœuds. La réponse contient n valeurs, donc l’espace est de O(n) . En plus de cela, la file contient environ le niveau le plus large et la récursion, la hauteur de l’arbre.

Q: Comment savoir où se termine un niveau dans une recherche en largeur d’abord ?

Lisez la taille de la file au début de chaque tour et prenez exactement ce nombre de nœuds. Deux autres méthodes fonctionnent également : conserver le niveau actuel et le niveau suivant dans deux listes distinctes, ou ajouter un marqueur à la file après chaque niveau.

Q: Le tableau est déjà stocké niveau par niveau. Pourquoi ne pas le lire par tranches ?

Pour ce format, cela fonctionne ainsi : le niveau d , avec la racine à 0, remplit les index 2^d-1 à 2^(d+1)-2 . Il suffit donc de collecter les valeurs non vides de chaque plage jusqu’à ce qu’une plage n’en contienne aucune. En entretien, on fournit généralement plutôt des objets nœud avec des pointeurs, et seule la file d’attente s’applique aussi à cette représentation.

MoyenParcours d’arbre File

+10

Le tableau tree contient un arbre binaire. 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 place vide, et des entrées -1 supplémentaires peuvent se trouver à la fin.

Retournez les valeurs des nœuds niveau par niveau : une liste par niveau, de la racine jusqu’au niveau le plus profond, avec les valeurs de gauche à droite.

Fonction

levelOrder(tree: integer-array) → integer-2d-array

treeinteger-array: l’arbre en ordre de tas, avec -1 pour une position vide
Renvoieinteger-2d-array: une liste de valeurs par niveau, le niveau supérieur en premier, chacune de gauche à droite

Contraintes

1 ≤ tree.length ≤ 32767
Chaque tree[i] vaut -1 ou une valeur telle que 0 ≤ tree[i] ≤ 1000.
tree[0] n'est jamais -1, donc l'arbre contient 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 la profondeur est d’au plus 14.

Exemples

Entrée: tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]
Sortie: [[4], [9, 2], [6, 8, 5], [3]]
Explication: L’indice 3 est vide, donc 9 n’a qu’un enfant droit, 6. Le troisième niveau contient 6, 8, 5, et le 3 à l’indice 9, sous 6, est seul au quatrième niveau.

Entrée: tree = [7, -1, -1]
Sortie: [[7]]
Explication: Les deux enfants de la racine sont -1, donc l’arbre est constitué du seul nœud 7 et comporte un niveau.

Entrée: tree = [1, 3, -1, 5, -1, -1, -1]
Sortie: [[1], [3], [5]]
Explication: Chaque nœud n’a qu’un enfant gauche : 3 à l’indice 1 et 5 à l’indice 3. Chaque niveau contient une valeur, et les entrées -1 à la fin n’ajoutent rien.

Pour aller plus loin

Peux-tu renvoyer les niveaux dans l’ordre en zigzag, le premier de gauche à droite, le deuxième de droite à gauche, et ainsi de suite, sans trier aucun niveau ?

Indices

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

0 sur 3 ouverts

Solution

Chaque niveau doit être présenté sous la forme de sa propre liste de gauche à droite. Une recherche en largeur utilisant une file d’attente visite les nœuds dans cet ordre et, au début de chaque tour, la file contient exactement un niveau : sa taille indique donc combien de nœuds traiter. Un parcours en profondeur qui suit également la profondeur de chaque nœud convient aussi.

Parcours en profondeur, classé par profondeur

Intuition

Parcourez l’arbre en profondeur, en transmettant à chaque nœud sa profondeur — 0 pour la racine — et conservez une liste par profondeur. Un nœud à la profondeur d ajoute sa valeur à la liste d, en créant cette liste si c’est le premier nœud rencontré à ce niveau.

Chaque liste est obtenue de gauche à droite, car le parcours termine le sous-arbre gauche d’un nœud avant d’entrer dans le sous-arbre droit. Parmi deux nœuds d’un même niveau, celui dont le chemin tourne à gauche à l’endroit où les chemins se séparent est atteint en premier. Dans l’exemple 1, l’ordre de visite 4, 9, 6, 3, 2, 8, 5 remplit [4], [9, 2], [6, 8, 5], [3].

Chaque nœud est visité une fois : temps O(n), avec une récursion aussi profonde que l’arbre, jusqu’à 14 niveaux.

Algorithme

Créez une liste vide de niveaux.
Visitez la racine avec une profondeur de 0.
Au nœud i avec une profondeur d, arrêtez-vous si i dépasse la fin ou si tree[i] vaut -1.
S’il n’y a que d listes, ajoutez-en une vide. Ajoutez tree[i] à la liste d.
Visitez 2i+1, puis 2i+2, tous deux avec une profondeur de d+1.

def levelOrder(tree):
    n = len(tree)
    levels = []

    def visit(i, depth):
        if i >= n or tree[i] == -1:
            return
        if depth == len(levels):  # the first node seen on this level
            levels.append([])
        levels[depth].append(tree[i])
        # Left before right, so every level fills from left to right.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return levels

Parcours en largeur, un niveau par tour

Intuition

Retire un nœud de la file et ajoute ses enfants, en commençant par celui de gauche. Le niveau d+1 n’entre que lorsque le niveau d sort ; les nœuds sortent donc niveau par niveau, de gauche à droite.

Pour découper ce flux en niveaux, lis la taille de la file au début d’un tour. Le niveau précédent a disparu et aucun nœud du niveau suivant n’est encore arrivé : la file contient donc exactement le niveau actuel. Prends autant de nœuds pour former une ligne ; leurs enfants attendront le tour suivant. Dans l’exemple 1, les tours prennent respectivement 1, 2, 3 et 1 nœuds.

Chaque nœud entre et sort de la file une seule fois : temps O(n). La file contient environ un niveau, soit au plus 8 192 nœuds au niveau le plus profond d’un arbre complet de 14 niveaux.

Algorithme

Place l’index 0 de la racine dans une file d’attente.
Tant que la file d’attente n’est pas vide, lis sa taille s et commence une ligne vide.
Retire s index. Pour chaque index i, ajoute tree[i] à la ligne.
Ajoute 2i+1, puis 2i+2, à la file d’attente si l’index se trouve dans le tableau et ne contient pas -1.
Ajoute la ligne à la réponse et commence le tour suivant.

from collections import deque


def levelOrder(tree):
    n = len(tree)
    levels = []
    queue = deque([0])  # node indexes; the root is never empty
    while queue:
        row = []
        for _ in range(len(queue)):  # exactly the nodes of the current level
            i = queue.popleft()
            row.append(tree[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
        levels.append(row)
    return levels

Pièges et cas limites

Lire la taille de la file pendant qu'on la vide. Dans while (j < queue.length), la longueur augmente à mesure que les enfants arrivent, donc le niveau suivant déborde sur la ligne actuelle.
Ajouter l'enfant droit avant l'enfant gauche, ou parcourir le sous-arbre droit en premier. Le deuxième niveau de l'exemple 1 devient alors [2, 9].
Omettre la vérification de limite child < n. Les enfants des nœuds les plus profonds se trouvent au-delà de la fin du tableau.
Retirer les éléments du début d'une liste sous forme de tableau simple, ce qui, dans de nombreux langages, décale toute la file à chaque fois. Utilisez une véritable file ou un index de tête.
Traiter -1 comme un nœud. Il n'entre jamais dans une ligne ni dans la file : [7, -1, -1] donne [[7]], et non [[7], []].

Questions fréquentes3

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

Les deux solutions visitent chaque nœud une fois : un temps de O(n) pour n nœuds. La réponse contient n valeurs, donc l’espace est de O(n). En plus de cela, la file contient environ le niveau le plus large et la récursion, la hauteur de l’arbre.

Comment savoir où se termine un niveau dans une recherche en largeur d’abord ?

Lisez la taille de la file au début de chaque tour et prenez exactement ce nombre de nœuds. Deux autres méthodes fonctionnent également : conserver le niveau actuel et le niveau suivant dans deux listes distinctes, ou ajouter un marqueur à la file après chaque niveau.

Le tableau est déjà stocké niveau par niveau. Pourquoi ne pas le lire par tranches ?

Pour ce format, cela fonctionne ainsi : le niveau d, avec la racine à 0, remplit les index 2^d-1 à 2^(d+1)-2. Il suffit donc de collecter les valeurs non vides de chaque plage jusqu’à ce qu’une plage n’en contienne aucune. En entretien, on fournit généralement plutôt des objets nœud avec des pointeurs, et seule la file d’attente s’applique aussi à cette représentation.

def levelOrder(tree):
    # Écrivez le code ici

Test #1

Test #2

Test #3

Argument

tree = [4, 9, 2, -1, 6, 8, 5, -1, -1, 3]

Résultat attendu

[[4], [9, 2], [6, 8, 5], [3]]