Binary Tree Level Order Traversal

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

Les solutions en largeur d’abord et en profondeur d’abord visitent chaque nœud une fois ; elles s’exécutent donc en O(n) pour n nœuds. La réponse elle-même contient n valeurs, donc l’espace est en O(n) . En outre, la file contient au plus environ le niveau le plus large, et la récursion, au plus la hauteur de l’arbre.

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

Lisez la taille de la file au début de chaque tour. À ce moment-là, la file contient exactement les nœuds d’un niveau ; en retirer ce nombre de nœuds permet donc de retirer le niveau, et rien de plus. Deux autres méthodes fonctionnent aussi : conserver le niveau actuel et le niveau suivant dans deux listes distinctes, ou ajouter un marqueur après chaque niveau.

Q: Peut-on effectuer un parcours en largeur avec une recherche en profondeur ?

Oui. Transmets à chaque nœud sa profondeur et ajoute sa valeur à la liste correspondant à cette profondeur. Tant que le parcours visite le sous-arbre gauche avant le sous-arbre droit, chaque liste se retrouve dans l’ordre de gauche à droite. C’est également en O(n) ; le parcours en largeur convient plus directement, car il produit les niveaux dans l’ordre.

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 occupe les index 2^d-1 à 2^(d+1)-2 , vous pouvez donc recueillir les valeurs non vides de chaque plage et vous arrêter à la première plage qui n’en contient aucune. En entretien, cependant, l’arbre se présente généralement sous la forme d’objets nœuds avec des pointeurs gauche et droit, sans index permettant de découper le tableau. Le parcours basé sur une file est ce qui s’adapte à cette forme et à des variantes telles que l’ordre en zigzag ou la vue depuis le côté droit.

MoyenParcours d’arbre File

+10

Vous disposez d’un arbre binaire stocké dans le tableau tree. La racine se trouve à l’index 0, les enfants du nœud à l’index i se trouvent aux index 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.

Renvoyez les valeurs des nœuds niveau par niveau : une liste contenant la valeur de la racine, puis une liste contenant les valeurs du niveau suivant, de gauche à droite, et ainsi de suite jusqu’au niveau le plus profond.

Fonction

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

treeinteger-array: l’arbre dans l’ordre du tas, avec -1 pour un emplacement vide
Renvoieinteger-2d-array: une liste de valeurs par niveau, en commençant par le niveau supérieur, 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: La racine 4 a pour enfants 9 et 2 aux index 1 et 2. L’index 3 est vide, donc le troisième niveau contient 6 (index 4, sous 9), puis 8 et 5 (aux index 5 et 6, sous 2). Le 3 à l’index 9 est l’enfant gauche de 6, 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 se compose du seul nœud 7 et possède 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 finales n’ajoutent rien.

+15 tests cachés à la soumission

Pour aller plus loin

Peux-tu renvoyer les niveaux 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 renvoyé sous forme de liste distincte, ordonnée de gauche à droite. Un parcours en largeur avec une file visite les nœuds exactement dans cet ordre. L’idée supplémentaire consiste à savoir où se termine un niveau : au début de chaque tour, la file contient tout le niveau courant, et rien d’autre ; sa taille indique donc combien de nœuds traiter. Un parcours en profondeur fonctionne également, à condition de conserver la profondeur de chaque nœud et de parcourir d’abord à gauche, puis à droite.

Parcours en profondeur, classé par profondeur

Intuition

Commençons par nous déplacer dans le tableau. L’enfant gauche de l’index i se trouve à l’index 2i+1 et l’enfant droit à l’index 2i+2. Un enfant est absent lorsque son index dépasse la fin du tableau ou contient -1. Dans l’exemple 1, les enfants de 9 (index 1) se trouvent aux index 3 et 4, qui contiennent -1 et 6 ; 9 n’a donc qu’un enfant droit.

Parcourons maintenant l’arbre en profondeur et transmettons à chaque nœud sa profondeur, 0 pour la racine. Gardons une liste par profondeur. Lorsque nous atteignons un nœud de profondeur d, ajoutons sa valeur à la liste d ; s’il n’y a encore que d listes, c’est le premier nœud d’un nouveau niveau, alors créons d’abord une nouvelle liste.

Pourquoi chaque niveau est-il parcouru de gauche à droite ? Le parcours termine tout le sous-arbre gauche d’un nœud avant d’entrer dans son sous-arbre droit. Prenons deux nœuds situés au même niveau : à l’endroit où leurs chemins depuis la racine se séparent, l’un va à gauche et l’autre à droite, et le parcours atteint d’abord celui de gauche. Dans l’exemple 1, l’ordre est 4, 9, 6, 3, 2, 8, 5, ce qui remplit les listes ainsi : [4], [9, 2], [6, 8, 5], [3].

Chaque nœud est visité une fois ; le temps d’exécution est donc de O(n) pour n nœuds, et les listes contiennent n valeurs. La récursion n’atteint que la profondeur de l’arbre, soit 15 niveaux au maximum ici. La version R utilise plutôt une pile explicite : elle empile l’enfant droit avant l’enfant gauche, afin que celui de gauche soit dépilé en premier, puis regroupe les valeurs par profondeur avec split.

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] est -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

Une file d’attente restitue les valeurs dans l’ordre où elles y sont entrées. Ajoute la racine. Puis, à plusieurs reprises, retire un nœud et ajoute ses enfants, en commençant par l’enfant gauche. Chaque nœud du niveau d+1 entre dans la file lorsque son parent du niveau d en sort ; ainsi, tous les nœuds du niveau d en sortent avant que ceux du niveau d+1 n’y sortent, et, au sein d’un niveau, les nœuds en sortent de gauche à droite.

On obtient ainsi un flux de valeurs dans l’ordre des niveaux. Pour le découper en niveaux, lis la taille de la file au début d’un tour. À ce moment-là, la file contient exactement le niveau courant : le niveau précédent a été retiré et aucun nœud du niveau suivant n’est encore arrivé. Retire ce nombre de nœuds et place-les dans une même liste. Les enfants qu’ils ajoutent appartiennent au tour suivant.

Dans l’exemple 1, la file commence par [4] : retire 1 nœud, la rangée [4], et 9, 2 y entrent. Retire 2 nœuds, la rangée [9, 2], et 6, 8, 5 y entrent. Retire 3 nœuds, la rangée [6, 8, 5], et 3 y entre. Retire 1 nœud, la rangée [3], et la file est vide.

Chaque nœud entre dans la file et en sort une seule fois, donc le temps d’exécution est O(n). La file contient au maximum environ un niveau, soit jusqu’à 16384 nœuds au niveau le plus profond d’un arbre complet de profondeur 14. Utilise une véritable file ou un index de tête : retirer le premier élément d’une simple liste sous forme de tableau déplace tous les éléments qui le suivent dans de nombreux langages.

Algorithme

Placez l’indice 0 de la racine dans une file d’attente.
Tant que la file d’attente n’est pas vide, lisez sa taille s et commencez une rangée vide.
Retirez s indices. Pour chaque indice i, ajoutez tree[i] à la rangée.
Ajoutez 2i+1, puis 2i+2, à la file d’attente si l’indice se trouve dans le tableau et ne contient pas -1.
Ajoutez la rangée à la réponse et commencez 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

Le parcours lui-même est court. Les bugs se trouvent dans les limites des niveaux et les emplacements vides.

Lire la taille de la file alors que vous êtes encore en train de la vider. Dans une boucle comme while (j < queue.length), la longueur augmente à mesure que les enfants arrivent, si bien que le niveau suivant déborde sur la ligne actuelle. Lisez la taille une fois, avant le début du tour.
Ajouter l’enfant droit avant le gauche. Chaque niveau est alors parcouru de droite à gauche. Il en va de même pour un parcours en profondeur qui visite d’abord le sous-arbre droit.
Traiter -1 comme une valeur. Un emplacement vide n’est pas un nœud, il n’entre donc jamais dans une ligne ni dans la file.
Oublier de vérifier les limites. Les enfants des nœuds les plus profonds peuvent se trouver au-delà de la fin du tableau ; vérifiez donc child < n avant de lire tree[child].
Renvoyer des niveaux vides. Les entrées -1 finales ne contiennent aucun nœud ; la réponse pour [7, -1, -1] est donc [[7]], et non [[7], []].

Questions fréquentes4

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

Les solutions en largeur d’abord et en profondeur d’abord visitent chaque nœud une fois ; elles s’exécutent donc en O(n) pour n nœuds. La réponse elle-même contient n valeurs, donc l’espace est en O(n). En outre, la file contient au plus environ le niveau le plus large, et la récursion, au plus la hauteur de l’arbre.

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

Lisez la taille de la file au début de chaque tour. À ce moment-là, la file contient exactement les nœuds d’un niveau ; en retirer ce nombre de nœuds permet donc de retirer le niveau, et rien de plus. Deux autres méthodes fonctionnent aussi : conserver le niveau actuel et le niveau suivant dans deux listes distinctes, ou ajouter un marqueur après chaque niveau.

Peut-on effectuer un parcours en largeur avec une recherche en profondeur ?

Oui. Transmets à chaque nœud sa profondeur et ajoute sa valeur à la liste correspondant à cette profondeur. Tant que le parcours visite le sous-arbre gauche avant le sous-arbre droit, chaque liste se retrouve dans l’ordre de gauche à droite. C’est également en O(n) ; le parcours en largeur convient plus directement, car il produit les niveaux dans l’ordre.

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 occupe les index 2^d-1 à 2^(d+1)-2, vous pouvez donc recueillir les valeurs non vides de chaque plage et vous arrêter à la première plage qui n’en contient aucune. En entretien, cependant, l’arbre se présente généralement sous la forme d’objets nœuds avec des pointeurs gauche et droit, sans index permettant de découper le tableau. Le parcours basé sur une file est ce qui s’adapte à cette forme et à des variantes telles que l’ordre en zigzag ou la vue depuis le côté droit.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

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