Binary Tree Zigzag Level Order Traversal

+10

On vous donne un arbre binaire stocké dans le tableau root. 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.

Renvoyez les valeurs des nœuds niveau par niveau, dans un ordre en zigzag : le niveau de la racine de gauche à droite, le suivant de droite à gauche, et ainsi de suite, en alternant jusqu’au niveau le plus profond. Cette méthode est également appelée parcours en spirale par niveaux.

Fonction

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

rootinteger-array: l’arbre en ordre de tas, avec -1 pour une case vide
Renvoieinteger-2d-array: une liste de valeurs par niveau, en commençant par le niveau supérieur, en alternant de gauche à droite et de droite à gauche

Contraintes

1 ≤ root.length ≤ 32767
Chaque root[i] vaut -1 ou est une valeur telle que 0 ≤ root[i] ≤ 10⁴.
Les valeurs des nœuds sont distinctes.
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 = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
Sortie: [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
Explication: En lisant de gauche à droite, les niveaux sont 8 ; 12, 5 ; 1, 9, 14 ; 4, 2, 11. Les niveaux 1 et 3 sont parcourus à l’envers : [5, 12] et [11, 2, 4].

Entrée: root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
Sortie: [[1], [3, 2], [4, 5, 6, 7]]
Explication: Un arbre complet de trois niveaux : le niveau du milieu s’inverse pour donner [3, 2] et le troisième va à nouveau de gauche à droite. Les deux entrées -1 à la fin correspondent aux emplacements vides des enfants de 4.

Pour aller plus loin

Peux-tu placer directement chaque valeur à sa place définitive dans sa ligne, sans rien inverser et sans deuxième pile ?

Solution

Les niveaux proviennent d’un parcours en largeur ordinaire. La nouveauté tient au sens : un niveau sur deux est inversé. Inverse les lignes impaires après les avoir construites, ou stocke chaque niveau dans une pile, qui restitue les éléments dans l’ordre inverse de leur empilement.

Par niveau, puis inverser un niveau sur deux

Intuition

Une file qui traite un niveau par tour renvoie chaque niveau de gauche à droite. Numérote les niveaux à partir de 0 à la racine : le parcours en zigzag lit les niveaux impairs de droite à gauche, donc inverser exactement ces lignes donne la réponse.

La recherche visite chaque nœud une fois et chaque inversion touche chaque valeur une fois de plus, donc le temps d’exécution est O(n).

Algorithme

Commence une file avec l’index 0.
À chaque tour, enregistre la longueur de la file s, retire s index pour former une nouvelle ligne, puis ajoute chacun de leurs enfants existants à la file, d’abord celui de gauche, puis celui de droite.
Si la réponse contient déjà un nombre impair de lignes, inverse la ligne.
Ajoute la ligne et continue jusqu’à ce que la file soit vide.

from collections import deque


def zigzagLevelOrder(root):
    n = len(root)
    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(root[i])
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and root[child] != -1:
                    queue.append(child)
        if len(levels) % 2 == 1:  # levels 1, 3, 5, ... read from right to left
            row.reverse()
        levels.append(row)
    return levels

Deux piles

Intuition

Conservez le niveau actuel dans une pile qui dépile dans le sens de lecture du niveau, et empilez les enfants de chaque nœud dépilé dans une deuxième pile. Lorsque la pile actuelle est vide, la deuxième contient le niveau suivant.

L’ordre d’empilement permet de faire fonctionner cette méthode. En dépilant de gauche à droite, empilez d’abord l’enfant gauche de chaque nœud, puis son enfant droit : l’enfant droit du nœud le plus à droite est empilé en dernier, de sorte que le niveau suivant est dépilé depuis son extrémité droite. En dépilant de droite à gauche, empilez d’abord l’enfant droit, puis le gauche ; l’enfant gauche du nœud le plus à gauche est alors empilé en dernier.

Exemple 1 : dépilez 8, empilez 12, 5. Dépilez 5, 12, puis empilez 14 depuis 5 et 9, 1 depuis 12. Dépilez 1, 9, 14, puis empilez 4, 2 depuis 9 et 11 depuis 14. Dépilez 11, 2, 4.

Chaque nœud est empilé et dépilé une fois : temps O(n), sans étape d’inversion.

Algorithme

Empilez l’index 0 de la racine et commencez à lire de gauche à droite.
Tant que la pile n’est pas vide, dépilez chaque index dans une nouvelle ligne et empilez les enfants existants de chaque nœud dépilé dans une deuxième pile : d’abord à gauche, puis à droite si vous lisez de gauche à droite, et d’abord à droite, puis à gauche dans le cas contraire.
Ajoutez la ligne à la réponse.
Faites de la deuxième pile la pile actuelle, inversez le sens et recommencez.

def zigzagLevelOrder(root):
    n = len(root)
    levels = []
    current = [0]  # a stack of node indexes; the root is never empty
    left_to_right = True
    while current:
        row = []
        upcoming = []  # the next level, pushed while this one pops
        while current:
            i = current.pop()
            row.append(root[i])
            # Push so that the next level pops out in its own direction.
            if left_to_right:
                children = (2 * i + 1, 2 * i + 2)
            else:
                children = (2 * i + 2, 2 * i + 1)
            for child in children:
                if child < n and root[child] != -1:
                    upcoming.append(child)
        levels.append(row)
        current = upcoming
        left_to_right = not left_to_right
    return levels

Pièges et cas limites

Inverser l’ordre dans lequel les enfants entrent dans une seule file. Les frères et sœurs échangent leurs places, mais les parents conservent leur ordre : le troisième niveau de l’exemple 1 donne [9, 1, 14].
Compter les niveaux à partir de 1. Chaque inversion décale d’un niveau, et l’exemple 1 donne [[8], [12, 5], [14, 9, 1], [4, 2, 11]].
Utiliser le même ordre d’empilement à chaque niveau de la version à deux piles. Le troisième niveau de l’exemple 1 est alors dépilé ainsi : [9, 1, 14].
Empiler les enfants dans la pile que vous êtes encore en train de dépiler. Ils en sortent avant le reste du niveau de leur parent.
Trier une rangée au lieu de l’inverser. Le dernier niveau de l’exemple 1 doit être [11, 2, 4], ce qu’aucun tri ne produit.

Questions fréquentes3

Quelle est la différence entre le parcours en zigzag et le parcours par niveaux ?

Ils parcourent les mêmes niveaux avec les mêmes nœuds. Le parcours par niveaux visite chaque niveau de gauche à droite ; le parcours en zigzag visite un niveau sur deux de droite à gauche, en commençant par le niveau sous la racine. Les deux s’exécutent en O(n) temps.

Le parcours en zigzag est-il identique au parcours en spirale d’un arbre ?

Oui, les deux noms décrivent le même parcours. Certains textes commencent le deuxième niveau par la gauche plutôt que par la droite, ce qui ne fait que décaler les changements de sens d'un niveau. Ici, le niveau de la racine va de gauche à droite et le suivant de droite à gauche.

Peut-on effectuer un parcours par niveaux en zigzag avec une deque ?

Oui. Garde chaque niveau dans la deque dans l’ordre de gauche à droite. Pour un niveau de gauche à droite, prends les nœuds à l’avant et ajoute leurs enfants, d’abord celui de gauche puis celui de droite, à l’arrière. Pour un niveau de droite à gauche, prends les nœuds à l’arrière et ajoute leurs enfants, d’abord celui de droite puis celui de gauche, à l’avant. Le nombre d’éléments à prendre au début d’un tour indique toujours le niveau.

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

Test #1

Test #2

Test #3

Argument

root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]

Résultat attendu

[[8], [5, 12], [1, 9, 14], [11, 2, 4]]