Binary Tree Right Side View

Q: Quelle est la complexité temporelle et spatiale de la vue du côté droit d’un arbre binaire ?

Le temps est de O(n) pour n nœuds, et aucune solution ne peut ignorer des nœuds, car le nœud le plus à droite d’un niveau peut se trouver n’importe où. L’espace est de O(w) pour la file, où w est le niveau le plus large, ou de O(h) pour le parcours en partant de la droite dans un arbre de h niveaux.

MoyenParcours d’arbre File

+10

Le tableau root 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.

Regarde l’arbre depuis son côté droit. À chaque niveau, tu vois exactement un nœud, celui qui est le plus à droite, et les autres sont masqués. Énumère ces valeurs depuis le niveau de la racine jusqu’au niveau le plus profond.

Fonction

rightSideView(root: integer-array) → integer-array

rootinteger-array: l’arbre en ordre de tas, avec -1 pour une case vide
Renvoieinteger-array: la valeur la plus à droite de chaque niveau, en commençant par le niveau supérieur

Contraintes

1 ≤ root.length ≤ 32767
Chaque root[i] vaut -1 ou une valeur telle que 0 ≤ root[i] ≤ 10⁴.
Les valeurs des nœuds sont distinctes.
root[0] n'est jamais -1, donc l'arbre possède 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 eux aussi vides, et l'arbre comporte au plus 14 niveaux.

Exemples

Entrée: root = [5, 2, 9, 7, 4, -1, 1, -1, 3]
Sortie: [5, 9, 1, 3]
Explication: Depuis la droite, tu vois 5, 9 et 1 (index 6). Le quatrième niveau ne contient que 3, à l’index 8 sous 7 dans le sous-arbre gauche. Rien à droite n’atteint cette profondeur, donc 3 est visible.

Entrée: root = [6, 0, -1, 8, -1, -1, -1]
Sortie: [6, 0, 8]
Explication: L’arbre est une chaîne d’enfants gauches : 6, 0, 8. Chaque niveau contient un nœud, donc tu les vois tous les trois, bien qu’aucun ne soit un enfant droit.

Entrée: root = [42]
Sortie: [42]
Explication: Un tableau de longueur 1 : la racine 42 n’a aucun emplacement enfant, et la vue correspond à cette unique valeur.

Pour aller plus loin

Comment obtiendriez-vous la vue de droite d’un arbre dans lequel chaque nœud peut avoir un nombre quelconque d’enfants, stockés dans une liste de gauche à droite ?

Indices

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

0 sur 3 ouverts

Solution

Vous voyez le nœud le plus à droite de chaque niveau, et il n’est pas nécessairement un enfant droit : la dernière valeur de l’exemple 1 se trouve dans le sous-arbre gauche. Une recherche en largeur fait de ce nœud le dernier de chaque parcours ; un parcours en profondeur qui va d’abord à droite le rencontre avant tout autre nœud de son niveau.

Parcours en largeur, dernier nœud de chaque niveau

Intuition

Parcours l’arbre niveau par niveau, un niveau par tour. Au début d’un tour, la file contient exactement un niveau, de gauche à droite. Le dernier indice retiré de la file pendant le tour correspond donc au nœud le plus à droite de ce niveau, et sa valeur est ajoutée à la réponse.

Dans l’exemple 1, les tours sont [5], [2, 9], [7, 4, 1] et [3], et leurs derniers éléments donnent 5, 9, 1, 3. C’est le niveau qui compte, pas le côté : 3 se trouve dans le sous-arbre gauche, mais il est seul à son niveau.

Chaque indice est ajouté et retiré de la file une seule fois, donc le temps d’exécution est de O(n). La file peut atteindre la largeur du niveau le plus large, soit O(n) dans le pire des cas.

Algorithme

Ajoutez l’indice de la racine 0 à la file.
Commencez un tour en enregistrant la longueur de la file s.
Retirez s indices de la file. Pour chaque indice i, ajoutez 2i+1 puis 2i+2 à la file s’ils sont inférieurs à la longueur du tableau et différents de -1.
Ajoutez la valeur du dernier indice retiré de la file pendant le tour.
Répétez jusqu’à ce que la file soit vide, puis renvoyez la réponse.

from collections import deque


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

Parcours en profondeur, enfant droit en premier

Intuition

Parcourez l’arbre en profondeur, en essayant l’enfant droit avant le gauche, et transmettez la profondeur, égale à 0 à la racine. La première fois que le parcours atteint la profondeur d, la réponse contient exactement d valeurs. Ajoutez alors la valeur du nœud et ignorez tous les nœuds suivants de ce niveau.

Ce premier nœud est celui le plus à droite : lorsque deux chemins vers un niveau se séparent, le parcours suit la branche droite jusqu’en bas avant de remonter vers la branche gauche. Dans l’exemple 1, le parcours visite 5, 9, 1, 2, 4, 7, 3 : il ignore 2, 4 et 7, dont les profondeurs ont déjà une valeur, et ajoute 3.

Chaque nœud est visité une seule fois, en temps O(n), avec un appel par niveau sur la pile, 14 au maximum.

Algorithme

Commence avec une réponse vide et la racine à la profondeur 0.
Ignore un index qui dépasse la fin du tableau ou contient -1.
Lorsque la longueur de la réponse est égale à la profondeur, ajoute la valeur : le parcours a atteint un nouveau niveau, et il l’a atteint par la droite.
Appelle d’abord récursivement l’enfant droit 2i+2, puis l’enfant gauche 2i+1, chacun à un niveau de profondeur supplémentaire.
Retourne la réponse.

def rightSideView(root):
    n = len(root)
    view = []

    def visit(i, depth):
        if i >= n or root[i] == -1:
            return
        if depth == len(view):  # the first node met on this level
            view.append(root[i])
        # Right before left, so the rightmost node of every level comes first.
        visit(2 * i + 2, depth + 1)
        visit(2 * i + 1, depth + 1)

    visit(0, 0)
    return view

Pièges et cas limites

Ne suivre que les enfants droits à partir de la racine. L’exemple 1 donne alors [5, 9, 1] et omet 3 ; l’exemple 2 donne [6].
Lire le dernier emplacement de chaque niveau, root[2^(d+1)-2]. Dans l’exemple 2, l’index 6 contient -1 ; le nœud visible est 8 à l’index 3.
Ignorer la vérification de la longueur à l’emplacement d’un enfant. Dans l’exemple 1, 3 est la dernière entrée : ses emplacements d’enfants 17 et 18 n’existent donc pas.
Mettre d’abord l’enfant droit dans la file tout en conservant le dernier nœud de chaque tour. Cela recueille la vue de gauche, [5, 2, 7, 3].
Laisser les nœuds ultérieurs remplacer les précédents dans le parcours de droite à gauche, ce qui donne également la vue de gauche.

Questions fréquentes3

Quelle est la complexité temporelle et spatiale de la vue du côté droit d’un arbre binaire ?

Le temps est de O(n) pour n nœuds, et aucune solution ne peut ignorer des nœuds, car le nœud le plus à droite d’un niveau peut se trouver n’importe où. L’espace est de O(w) pour la file, où w est le niveau le plus large, ou de O(h) pour le parcours en partant de la droite dans un arbre de h niveaux.

Une recherche en profondeur privilégiant la gauche peut-elle résoudre ce problème ?

Oui, si tu remplaces la valeur au lieu de conserver la première. Un parcours de gauche à droite rencontre les nœuds de chaque niveau de gauche à droite : stocke donc la valeur de chaque nœud à sa profondeur et laisse les nœuds suivants remplacer les précédents. Chaque profondeur se termine avec sa valeur la plus à droite. La complexité reste O(n), mais une écriture est effectuée par nœud.

Dois-je utiliser une recherche en largeur ou en profondeur ici ?

Les deux sont linéaires. La recherche en largeur suit la définition, un niveau par tour. La recherche en profondeur ne conserve que le chemin actuel, ce qui économise de la mémoire dans un arbre large, et sa forme récursive est plus courte de quelques lignes.

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

Test #1

Test #2

Test #3

Argument

root = [5, 2, 9, 7, 4, -1, 1, -1, 3]

Résultat attendu

[5, 9, 1, 3]