Symmetric Tree

Q: Quelle est la complexité temporelle de l’arbre symétrique ?

Chaque nœud réel est comparé une fois, dans le cadre d’une paire symétrique, donc le temps est O(n) . Les versions récursive et avec pile utilisent un espace supplémentaire de O(h) pour les paires en attente le long du chemin actuel. La version niveau par niveau conserve un niveau en mémoire, soit O(w) pour le niveau le plus large.

Q: Comment vérifier si un arbre binaire est symétrique sans récursion ?

Conservez une pile ou une file de paires de nœuds qui doivent être symétriques, en commençant par les deux enfants de la racine. Retirez une paire, échouez en cas de différence, puis ajoutez la paire extérieure et la paire intérieure de leurs enfants. Si la pile se vide sans qu’aucune différence ne soit détectée, l’arbre est symétrique.

Q: Quelle est la différence entre un arbre symétrique et deux arbres identiques ?

Deux arbres sont identiques lorsque vous comparez le gauche avec le gauche et le droit avec le droit. Un arbre est symétrique lorsque son sous-arbre gauche est identique à l’image miroir de son sous-arbre droit ; la comparaison croise donc les côtés : le gauche avec le droit et le droit avec le gauche. Le même code de vérification des paires résout les deux problèmes en inversant les paires d’enfants.

Q: Un arbre avec un seul nœud est-il symétrique ?

Oui. Un nœud unique a deux emplacements vides pour ses enfants, et deux emplacements vides se reflètent l’un l’autre. Une racine avec exactement un enfant n’est jamais symétrique, car cet enfant fait face à un emplacement vide.

FacileParcours d’arbre

+10

On vous donne un arbre binaire stocké dans le tableau tree en ordre par niveau. 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 un emplacement vide, et le tableau peut se terminer par des entrées -1 supplémentaires. Renvoyez true si l’arbre est son propre reflet par rapport à une ligne verticale passant par la racine, et false sinon. La forme et les valeurs doivent toutes deux correspondre.

Fonction

isSymmetric(tree: integer-array) → boolean

treeinteger-array: l’arbre binaire par ordre de niveau, avec -1 pour une place vide
Renvoieboolean: true si l’arbre est symétrique, false sinon

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 possède 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 = [1, 2, 2, 3, 4, 4, 3]
Sortie: true
Explication: Pliez l’arbre en deux au milieu. Les deux 2 aux index 1 et 2 se rejoignent, les 3 extérieurs aux index 3 et 6 se rejoignent, et les 4 intérieurs aux index 4 et 5 se rejoignent.

Entrée: tree = [1, 2, 2, -1, 3, -1, 3]
Sortie: false
Explication: Les deux 3 restent suspendus à droite de leurs parents. Dans une image miroir, l’enfant droit du 2 de gauche (index 4) doit faire face à l’enfant gauche du 2 de droite (index 5), et l’index 5 est vide.

Entrée: tree = [4, 6, 6, 5, -1, -1, 9]
Sortie: false
Explication: La forme est une image miroir : l’index 3 fait face à l’index 6 et les deux contiennent un nœud. Leurs valeurs diffèrent, 5 contre 9, donc l’arbre n’est pas symétrique.

+16 tests cachés à la soumission

Pour aller plus loin

Si la forme est symétrique, mais que certaines valeurs ne le sont pas, quel est le nombre minimal de valeurs de nœuds à modifier pour rendre l’arbre symétrique ?

Indices

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

0 sur 3 ouverts

Solution

La symétrie est une propriété des paires. Chaque nœud a un partenaire à l’emplacement symétrique de l’autre côté de la racine, et le partenaire d’un enfant gauche est un enfant droit. Vous ne comparez donc jamais un nœud à ses propres enfants : vous parcourez les deux moitiés de l’arbre simultanément dans des directions opposées, comparez la structure et la valeur de chaque paire, puis vous vous arrêtez à la première paire qui ne correspond pas.

Comparez chaque niveau avec son inverse

Intuition

D’abord, voyons comment se déplacer dans le tableau. Le nœud à l’indice i a son enfant gauche à l’indice 2*i+1 et son enfant droit à l’indice 2*i+2. Un enfant est réel uniquement si son indice se trouve dans le tableau et si la valeur à cet indice n’est pas -1. Dans [1, 2, 2, 3, 4, 4, 3], la racine 1 a ses enfants aux indices 1 et 2, et le 2 à l’indice 1 a ses enfants aux indices 3 et 4.

Examinons maintenant l’arbre niveau par niveau. Une image miroir se lit de la même façon de gauche à droite que de droite à gauche ; chaque niveau, écrit avec ses emplacements vides, doit donc se lire de la même façon dans les deux sens. Dans le premier exemple, les niveaux sous la racine sont 2 2 et 3 4 4 3. Dans le second, ils sont 2 2, puis -1 3 -1 3 ; inversé, cela donne 3 -1 3 -1, donc la réponse est false.

Les emplacements vides doivent rester dans la ligne. Sans eux, le niveau inférieur du second exemple serait 3 3 et le test serait réussi. Ajoutez une entrée pour chaque emplacement d’enfant de chaque nœud réel du niveau, -1 pour un emplacement vide ; les enfants des emplacements vides sont eux aussi vides, ils n’ajoutent donc rien. Chaque nœud est visité une seule fois, donc le temps d’exécution est O(n), et un seul niveau est conservé en mémoire à la fois, soit O(w) pour le niveau le plus large w.

Algorithme

Commencez avec une liste contenant l’index de la racine 0.
Pour chaque index de la liste, de gauche à droite, notez les deux emplacements des enfants : la valeur de l’enfant s’il existe, -1 s’il est vide. Récupérez les enfants existants pour le niveau suivant.
Si cette ligne d’emplacements des enfants diffère de son inverse, renvoyez false.
Passez au niveau suivant et répétez jusqu’à ce qu’il soit vide, puis renvoyez true.

def isSymmetric(tree):
    n = len(tree)
    level = [0]  # the real nodes of one level, left to right
    while level:
        row = []  # the child spots under this level, -1 for an empty one
        next_level = []
        for i in level:
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    row.append(tree[child])
                    next_level.append(child)
                else:
                    row.append(-1)
        if row != row[::-1]:
            return False
        level = next_level
    return True

Récursivité sur des paires en miroir

Intuition

Au lieu de comparer des niveaux entiers, comparez deux sous-arbres : le sous-arbre gauche de la racine, qui commence à l’indice 1, et son sous-arbre droit, qui commence à l’indice 2. Deux positions sont symétriques lorsqu’elles sont toutes les deux vides, ou lorsqu’elles contiennent la même valeur et que leurs enfants se croisent. L’enfant gauche de l’une est symétrique de l’enfant droit de l’autre (la paire extérieure), et l’enfant droit de l’une est symétrique de l’enfant gauche de l’autre (la paire intérieure).

Dans le premier exemple, mirrors(1, 2) compare les deux 2, puis appelle mirrors(3, 6) pour les 3 extérieurs et mirrors(4, 5) pour les 4 intérieurs. Chacun de ces appels ne trouve que des positions vides en dessous et renvoie true. Dans le deuxième exemple, mirrors(4, 5) trouve un 3 à l’indice 4 face à une position vide à l’indice 5, renvoie false, et le false remonte jusqu’en haut.

Chaque nœud réel appartient à au plus une paire, donc la complexité temporelle est O(n). La pile d’appels est aussi profonde que l’arbre, soit O(h), ce qui représente au plus 14 cadres ici.

Algorithme

Écris mirrors(a, b). Un emplacement est vide si son index dépasse la fin ou contient -1. Si les deux emplacements sont vides, renvoie true ; si un seul l’est, renvoie false.
Si tree[a] et tree[b] sont différents, renvoie false.
Sinon, renvoie mirrors(2*a+1, 2*b+2) et mirrors(2*a+2, 2*b+1).
Renvoie mirrors(1, 2). Une racine sans enfants donne deux emplacements vides, ce qui vaut true.

def isSymmetric(tree):
    n = len(tree)

    def mirrors(a, b):
        # Spots a and b must hold the same value, or both be empty.
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a or empty_b:
            return empty_a and empty_b
        return (tree[a] == tree[b]
                and mirrors(2 * a + 1, 2 * b + 2)   # outer pair
                and mirrors(2 * a + 2, 2 * b + 1))  # inner pair

    return mirrors(1, 2)

Empilement explicite de paires symétriques

Intuition

La récursion n’a besoin que d’une chose : les paires qu’il reste à vérifier. Garde ces paires dans ta propre pile et les appels disparaissent. Commence par la paire (1, 2). Dépile une paire. Si les deux positions sont vides, il n’y a rien en dessous, alors continue. Si l’une est vide ou si les valeurs diffèrent, l’arbre n’est pas symétrique. Sinon, empile la paire extérieure (2*a+1, 2*b+2) et la paire intérieure (2*a+2, 2*b+1).

L’ordre dans lequel tu vérifies les paires n’a pas d’importance, car l’arbre est symétrique uniquement si toutes les paires correspondent. Une pile donne un parcours en profondeur ; une file donnerait un parcours par niveaux et fonctionnerait de la même manière. Le troisième exemple s’arrête à sa première paire incorrecte, (3, 6), qui contient 5 et 9.

Chaque dépilement traite une paire et chaque nœud réel appartient à au plus une paire, donc le temps d’exécution est O(n). La pile conserve environ une paire en attente par niveau du chemin actuel, soit O(h) d’espace, et il n’y a pas de limite de récursion à prendre en compte.

Algorithme

Empile la paire (1, 2).
Dépile une paire (a, b). Si les deux positions sont vides (indice au-delà de la fin ou -1), passe à la paire suivante.
Si une seule position est vide, ou si tree[a] diffère de tree[b], renvoie false.
Empile (2*a+1, 2*b+2) et (2*a+2, 2*b+1).
Lorsque la pile est vide, renvoie true.

def isSymmetric(tree):
    n = len(tree)
    stack = [(1, 2)]  # pairs of spots that must mirror each other
    while stack:
        a, b = stack.pop()
        empty_a = a >= n or tree[a] == -1
        empty_b = b >= n or tree[b] == -1
        if empty_a and empty_b:
            continue
        if empty_a or empty_b or tree[a] != tree[b]:
            return False
        stack.append((2 * a + 1, 2 * b + 2))  # outer pair
        stack.append((2 * a + 2, 2 * b + 1))  # inner pair
    return True

Pièges et cas limites

La plupart des mauvaises réponses comparent la mauvaise paire de nœuds ou oublient qu’un emplacement vide fait partie de la forme.

Vérifier chaque sous-arbre séparément. Le sous-arbre gauche n’a pas besoin d’être symétrique à lui seul : dans [1, 2, 2, 3, 4, 4, 3], le sous-arbre 2, 3, 4 ne l’est pas, contrairement à l’arbre entier. Il doit être le reflet du sous-arbre droit.
Associer les enfants de la mauvaise façon. L’enfant gauche d’un côté fait face à l’enfant droit de l’autre : (2*a+1, 2*b+2) et (2*a+2, 2*b+1), jamais (2*a+1, 2*b+1).
Comparer uniquement les valeurs. Si l’on retire les emplacements vides de [1, 2, 2, -1, 3, -1, 3], chaque niveau se lit de la même façon dans les deux sens, et pourtant l’arbre n’est pas symétrique. Conservez -1 dans la ligne d’un niveau ou vérifiez si l’emplacement est vide lors du test des paires.
Lire au-delà de la fin. Un indice situé au-delà de la fin du tableau correspond à un emplacement vide. Vérifiez a < n avant de lire tree[a] ; un arbre composé d’un seul nœud n’a ni indice 1 ni indice 2.
S’arrêter à la première paire correspondante. Une seule paire correcte ne prouve rien ; ne renvoyez true qu’après avoir vérifié toutes les paires.
Confondre le décalage en Lua et en R, où les tableaux commencent à 1. Gardez les indices des nœuds à base 0 pour le calcul 2*i+1 et lisez tree[i + 1].

Questions fréquentes4

Quelle est la complexité temporelle de l’arbre symétrique ?

Chaque nœud réel est comparé une fois, dans le cadre d’une paire symétrique, donc le temps est O(n). Les versions récursive et avec pile utilisent un espace supplémentaire de O(h) pour les paires en attente le long du chemin actuel. La version niveau par niveau conserve un niveau en mémoire, soit O(w) pour le niveau le plus large.

Comment vérifier si un arbre binaire est symétrique sans récursion ?

Conservez une pile ou une file de paires de nœuds qui doivent être symétriques, en commençant par les deux enfants de la racine. Retirez une paire, échouez en cas de différence, puis ajoutez la paire extérieure et la paire intérieure de leurs enfants. Si la pile se vide sans qu’aucune différence ne soit détectée, l’arbre est symétrique.

Quelle est la différence entre un arbre symétrique et deux arbres identiques ?

Deux arbres sont identiques lorsque vous comparez le gauche avec le gauche et le droit avec le droit. Un arbre est symétrique lorsque son sous-arbre gauche est identique à l’image miroir de son sous-arbre droit ; la comparaison croise donc les côtés : le gauche avec le droit et le droit avec le gauche. Le même code de vérification des paires résout les deux problèmes en inversant les paires d’enfants.

Un arbre avec un seul nœud est-il symétrique ?

Oui. Un nœud unique a deux emplacements vides pour ses enfants, et deux emplacements vides se reflètent l’un l’autre. Une racine avec exactement un enfant n’est jamais symétrique, car cet enfant fait face à un emplacement vide.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

tree = [1, 2, 2, 3, 4, 4, 3]

Attendu

true

Symmetric Tree

Fonction

Contraintes

Exemples

Indices

Solution

Comparez chaque niveau avec son inverse

Récursivité sur des paires en miroir

Empilement explicite de paires symétriques

Pièges et cas limites

Questions fréquentes4

Problèmes similaires