Invert Binary Tree

+10

Tu reçois un arbre binaire stocké dans le tableau tree en ordre par niveaux. 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 position vide, et le tableau peut se terminer par des entrées -1 supplémentaires.

Inverse l’arbre : échange les enfants gauche et droit de chaque nœud afin que l’arbre entier devienne son image miroir. Renvoie l’arbre inversé sous la même forme, sans entrées -1 à la fin.

Fonction

invertTree(tree: integer-array) → integer-array

treeinteger-array: l’arbre binaire dans l’ordre par niveaux, avec -1 pour une position vide
Renvoieinteger-array: l’arbre miroir en parcours par niveaux, sans entrées -1 à la fin

Contraintes

1 ≤ tree.length ≤ 16383
Chaque tree[i] est -1 ou une valeur telle que 0 ≤ tree[i] ≤ 1000.
tree[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 la profondeur est au plus de 14.

Exemples

Entrée: tree = [5, 3, 8, 1, 4, -1, 9]
Sortie: [5, 8, 3, 9, -1, 4, 1]
Explication: Les enfants de la racine 3 et 8 échangent leurs places. Sous eux, 1 et 4, qui se trouvaient sous 3, reviennent sous la forme de 4 et 1, et 8, qui n'avait qu'un enfant droit, 9, l'a maintenant à gauche.

Entrée: tree = [2, 7, -1, 6]
Sortie: [2, -1, 7, -1, -1, -1, 6]
Explication: La chaîne 2, 7, 6 penche à gauche et son reflet penche à droite. Le 7 passe de l’indice 1 à l’indice 2 et le 6 de l’indice 3 à l’indice 6, la réponse est donc plus longue que l’entrée, avec -1 dans chaque emplacement vide avant le dernier nœud.

Entrée: tree = [1, -1, -1]
Sortie: [1]
Explication: Un nœud unique est son propre miroir. Les deux entrées -1 sont du remplissage, et la réponse supprime chaque -1 à la fin.

+14 tests cachés à la soumission

Pour aller plus loin

Comment vérifieriez-vous qu’un arbre est son propre miroir, en utilisant les mêmes paires d’indices, mais sans construire la copie inversée ?

Indices

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

0 sur 3 ouverts

Solution

Inverser un arbre signifie que chaque nœud échange ses sous-arbres gauche et droit, jusqu’en bas. Avec des objets nœud, cela correspond à un échange par nœud. Dans cette représentation sous forme de tableau, la position d’un nœud est son index : échanger deux sous-arbres signifie donc déplacer tous les nœuds qu’ils contiennent. La solution consiste à construire le résultat dans un nouveau tableau et à copier chaque nœud directement à son index miroir, en faisant suivre des paires d’index pendant le parcours : l’emplacement actuel du nœud et celui où il doit aller.

Récursion qui place chaque nœud à son indice miroir

Intuition

Tout d’abord, voyons comment se déplacer dans le tableau. Le nœud à l’index i a son enfant gauche à l’index 2*i+1 et son enfant droit à l’index 2*i+2. Un enfant n’existe que si son index se trouve dans le tableau et que la valeur à cet index n’est pas -1. Dans [5, 3, 8, 1, 4, -1, 9], la racine 5 a 3 et 8 aux index 1 et 2, et le 8 à l’index 2 a un emplacement vide à gauche à l’index 5 et le 9 à l’index 6.

Voyons maintenant le miroir. La racine reste à l’index 0. Le sous-arbre gauche d’un nœud devient le sous-arbre droit de sa copie miroir, et son sous-arbre droit devient le sous-arbre gauche. Ainsi, si le nœud à l’index src se retrouve à l’index dst dans le résultat, son enfant gauche se retrouve à l’index 2*dst+2 et son enfant droit à l’index 2*dst+1. Écris place(src, dst) : copie la valeur, puis appelle place(2*src+1, 2*dst+2) et place(2*src+2, 2*dst+1). Un emplacement vide entraîne un retour immédiat. Dans le premier exemple, le 3 à l’index 1 se retrouve à l’index 2, donc son enfant gauche 1 se retrouve à l’index 6 et son enfant droit 4 à l’index 5.

Un nœud ne change jamais de niveau ; son index miroir reste donc dans le même niveau que son index d’origine. Arrondis la longueur au nombre entier supérieur de niveaux (1, 3, 7, 15, ...), remplis autant d’emplacements avec -1, puis supprime les entrées -1 finales à la fin. Dans le deuxième exemple, la longueur 4 est arrondie à 7, ce qui laisse de la place pour le 6 à l’index 6.

Chaque nœud est placé une seule fois, et le résultat est rempli et réduit une seule fois : le temps d’exécution est O(n) pour un tableau de longueur n. Le résultat utilise O(n) mémoire et la pile d’appels O(h), soit au plus 14 niveaux ici, ce qui rend la récursion sûre dans ce problème.

Algorithme

Arrondis la longueur à la valeur supérieure size = 2^k - 1 et remplis un tableau de sortie de cette taille avec -1.
Écris place(src, dst) : si src dépasse la fin ou si tree[src] vaut -1, retourne.
Sinon, définis out[dst] = tree[src], puis appelle place(2*src+1, 2*dst+2) et place(2*src+2, 2*dst+1).
Appelle place(0, 0), supprime les entrées -1 finales et retourne le résultat.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size

    def place(src, dst):
        if src >= n or tree[src] == -1:
            return
        out[dst] = tree[src]
        place(2 * src + 1, 2 * dst + 2)  # the left subtree goes to the right
        place(2 * src + 2, 2 * dst + 1)  # the right subtree goes to the left

    place(0, 0)
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Parcours en largeur avec une file de paires d’indices

Intuition

Les mêmes paires fonctionnent sans récursion. Placez (0, 0) dans une file : la racine et l’emplacement où elle va. Prenez une paire (src, dst) au début de la file, copiez tree[src] dans out[dst], puis ajoutez à la file chaque enfant réel avec sa destination inversée : l’enfant gauche 2*src+1 avec 2*dst+2, l’enfant droit 2*src+2 avec 2*dst+1.

C’est l’inversion itérative classique. Avec des objets nœuds, vous prenez un nœud dans la file, échangez ses deux enfants et les ajoutez à la file. Ici, l’échange est écrit à l’index de destination à la place, car le tableau ne peut pas échanger deux sous-arbres entiers en une seule étape. Chaque nœud réel entre une fois dans la file, avec l’emplacement exact auquel il appartient, si bien que la sortie contient chaque nœud à sa place symétrique. Dans le premier exemple, les paires obtenues sont (0, 0), (1, 2), (2, 1), (3, 6), (4, 5), (6, 3).

Le temps d’exécution est O(n). La file contient au plus un niveau et un peu plus, soit O(w) pour le niveau le plus large w, en plus de la sortie O(n). Il n’y a pas de pile d’appels susceptible de déborder, donc cette version s’applique telle quelle aux arbres profonds basés sur des pointeurs.

Algorithme

Arrondis la longueur au niveau entier supérieur et remplis une sortie de cette taille avec -1.
Place la paire (0, 0) dans une file.
Prends une paire (src, dst) au début de la file et définis out[dst] = tree[src].
Ajoute à la file (2*src+1, 2*dst+2) et (2*src+2, 2*dst+1) pour chaque enfant qui se trouve dans le tableau et qui n’est pas -1.
Lorsque la file est vide, supprime les entrées -1 finales et renvoie la sortie.

def invertTree(tree):
    n = len(tree)
    size = 1
    while size < n:  # round up to whole levels, so every mirrored index fits
        size = 2 * size + 1
    out = [-1] * size
    queue = [(0, 0)]  # pairs: index in tree, index of its mirrored spot in out
    head = 0
    while head < len(queue):
        src, dst = queue[head]
        head += 1
        out[dst] = tree[src]
        left, right = 2 * src + 1, 2 * src + 2
        if left < n and tree[left] != -1:
            queue.append((left, 2 * dst + 2))  # the left child goes to the right
        if right < n and tree[right] != -1:
            queue.append((right, 2 * dst + 1))  # the right child goes to the left
    last = size - 1
    while out[last] == -1:  # trim the trailing -1 entries
        last -= 1
    return out[:last + 1]

Pièges et cas limites

Le miroir lui-même est facile à décrire. Les erreurs viennent du tableau : sa taille, sa fin et ce que déplace réellement l’échange de deux entrées.

Échanger tree[2*i+1] et tree[2*i+2] sur place. Cela échange deux valeurs, mais pas les sous-arbres qui se trouvent en dessous. Échanger les index 1 et 2 dans le premier exemple laisse 1 et 4 suspendus sous le 8.
Créer une sortie aussi longue que l’entrée. Un nœud miroir peut se retrouver au-delà du dernier index de l’entrée, comme le fait le 6 dans le deuxième exemple. Dimensionnez la sortie pour qu’elle couvre des niveaux entiers.
Oublier de tronquer. La réponse ne contient pas de -1 à la fin, aussi bien pour les entrées complétées que pour les arbres dont le miroir se termine avant la fin de l’entrée.
Inverser tout le tableau. Cela mélange les niveaux : la dernière feuille deviendrait la racine.
Omettre la vérification des limites. L’index d’un enfant peut dépasser la fin de l’entrée, car le tableau peut s’arrêter juste après le dernier nœud.
Confondre le décalage en Lua et en R, où les tableaux commencent à 1. Gardez les index à base 0 pour le calcul 2*i+1 et lisez tree[i + 1].

Questions fréquentes4

Que signifie inverser un arbre binaire ?

Inverser un arbre binaire le transforme en son image miroir : à chaque nœud, les sous-arbres gauche et droit échangent leurs places. La racine reste à sa place, la feuille la plus à gauche devient celle la plus à droite, et une chaîne gauche devient une chaîne droite. Inverser deux fois redonne l’arbre d’origine.

Quelle est la complexité temporelle de l’inversion d’un arbre binaire ?

Chaque nœud est visité une fois, donc la complexité temporelle est de O(n). Une solution récursive utilise un espace de pile de O(h) pour un arbre de profondeur h, tandis qu’une solution basée sur une file utilise O(w) pour le niveau le plus large. Dans cette version avec tableau, la réponse elle-même est un nouveau tableau, ce qui ajoute O(n).

Comment inverser un arbre binaire sans récursion ?

Utilisez une file ou une pile. Commencez par la racine et, chaque fois que vous retirez un nœud, échangez ses enfants gauche et droit, puis ajoutez les enfants. Chaque nœud est échangé une seule fois, quel que soit l’ordre dans lequel la structure vous les fournit. Dans la représentation sous forme de tableau, vous mettez plutôt en file des paires d’indices et placez chaque nœud directement à son emplacement miroir.

Pourquoi l’inversion d’un arbre binaire inverse-t-elle chaque niveau ?

La symétrie inverse la gauche et la droite partout, si bien que les nœuds de chaque niveau apparaissent dans l’ordre opposé. Dans le stockage en ordre par niveau, cela signifie que la tranche du tableau correspondant à chaque niveau est inversée : la tranche [1, 4, -1, 9] du premier exemple devient [9, -1, 4, 1]. Inverser chaque niveau après avoir complété le dernier avec -1 constitue une troisième solution en O(n), qui ne fonctionne que pour cette disposition du tableau.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

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

Attendu

[5, 8, 3, 9, -1, 4, 1]