Left View of Binary Tree

+10

Vous obtenez un arbre binaire sous forme du tableau root en ordre de tas : la racine se trouve à l’index 0, les enfants de l’index i se trouvent aux index 2*i+1 (à gauche) et 2*i+2 (à droite), et -1 marque un emplacement vide. Le tableau peut se terminer par des entrées -1 supplémentaires.

Placez-vous à gauche de l’arbre. À chaque niveau, vous voyez un nœud, celui le plus à gauche ; le reste du niveau se cache derrière lui. Renvoyez les valeurs que vous voyez, du niveau supérieur vers le bas.

Fonction

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

rootinteger-array: l’arbre dans l’ordre du tas, avec -1 pour une case vide
Renvoieinteger-array: la valeur la plus à gauche 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 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 l'arbre comporte au plus 14 niveaux.

Exemples

Entrée: root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]
Sortie: [3, 8, 6, 1]
Explication: 8 est une feuille, donc les troisième et quatrième niveaux ne contiennent que 6 (indice 6) et 1 (indice 13), tous deux sous l’enfant droit 5. Tu les vois quand même : [3, 8, 6, 1].

Entrée: root = [10, -1, -1]
Sortie: [10]
Explication: Les index 1 et 2 contiennent -1, donc 10 n’a pas d’enfants et la vue ne montre que la racine.

Entrée: root = [1, 2, 3, 4, 5, 6, 7]
Sortie: [1, 2, 4]
Explication: Un arbre complet de trois niveaux. Les positions les plus à gauche des niveaux sont les index 0, 1 et 3, qui contiennent 1, 2 et 4.

Pour aller plus loin

Le niveau d remplit les index 2^d-1 à 2^(d+1)-2. Peux-tu construire la vue en parcourant ces plages, sans file ni récursion ? Quel est le coût sur un tableau complété par du remplissage ?

Solution

Suivre les enfants gauches depuis la racine échoue lorsque le sous-arbre gauche est plus court : dans le premier exemple, les niveaux inférieurs sont visibles à travers le sous-arbre droit. Tu veux le premier nœud de chaque niveau. La recherche en largeur te donne chaque niveau de gauche à droite ; un parcours en profondeur qui commence par la gauche rencontre d’abord le nœud le plus à gauche de chaque niveau.

Parcours en largeur, premier nœud de chaque niveau

Intuition

Une file traitée par tours vous donne les niveaux un par un. Au début d’un tour, la file contient exactement un niveau, de gauche à droite, car chaque enfant ajouté pendant le tour est placé derrière celui-ci. Retirez autant d’indices, ajoutez les enfants de chacun à la file en commençant par ceux de gauche, et conservez la première valeur.

Dans le premier exemple, les tours sont [3], [8, 5], [6] et [1], et ils conservent 3, 8, 6 et 1. Le 8 n’ajoute rien, car les emplacements de ses enfants, 3 et 4, contiennent -1.

Chaque nœud entre dans la file et en sort une fois : O(n) en temps. La file peut contenir un niveau entier, jusqu’à 8192 indices dans un arbre complet de 14 niveaux.

Algorithme

Commencez une file contenant l’indice 0, et une réponse vide.
Tant que la file n’est pas vide, soit s sa taille et retirez s indices. Ajoutez la valeur du premier.
Pour chaque indice i retiré, ajoutez 2i+1 à la file, puis 2i+2, en ignorant les indices au-delà de la fin et les entrées égales à -1.

from collections import deque


def leftView(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 == 0:
                view.append(root[i])  # the first 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 gauche en premier

Intuition

Parcourez l’arbre en profondeur, le sous-arbre gauche avant le droit, et transmettez la profondeur de chaque nœud. Le premier nœud atteint par le parcours à la profondeur d est le plus à gauche du niveau d. Prenez le nœud le plus à gauche x d’un niveau et n’importe quel nœud y à sa droite : au dernier nœud où leurs chemins se rejoignent, x part à gauche et y à droite, et le parcours termine la branche gauche avant de tourner à droite.

Le parcours descend d’un niveau à la fois ; lorsqu’il atteint pour la première fois la profondeur d, la réponse contient donc exactement d valeurs. Enregistrez un nœud lorsque d est égal à la longueur de la réponse ; aucun ensemble des profondeurs déjà visitées n’est nécessaire.

Chaque nœud est visité une fois, en temps O(n), et la mémoire contient un appel par niveau, 14 au maximum ici. La version R conserve sa propre pile et empile l’enfant droit avant le gauche.

Algorithme

Crée un résultat vide et appelle visit(0, 0).
Dans visit(i, d), retourne immédiatement si i est en dehors du tableau ou si root[i] vaut -1.
Si d est égal à la longueur du résultat, le parcours a atteint le niveau d pour la première fois : ajoute root[i].
Appelle visit(2i+1, d+1), puis visit(2i+2, d+1).
Retourne le résultat une fois le premier appel terminé.

def leftView(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])
        # Left before right, so the leftmost node of every level comes first.
        visit(2 * i + 1, depth + 1)
        visit(2 * i + 2, depth + 1)

    visit(0, 0)
    return view

Pièges et cas limites

Suivre uniquement les enfants gauches à partir de la racine. Dans le premier exemple, cela s’arrête à 8 et manque 6 et 1.
Lire le premier emplacement de chaque niveau, root[2^d-1]. Dans le premier exemple, le premier emplacement du troisième niveau, à l’index 3, contient -1, tandis que son seul nœud se trouve à l’index 6.
Visiter d’abord l’enfant droit lors du parcours en profondeur. Le premier nœud rencontré à chaque niveau est alors celui le plus à droite.
Lire un enfant sans vérifier les limites. Le 1 à l’index 13 a des emplacements d’enfants 27 et 28, au-delà de la fin du tableau de 14 éléments.

Questions fréquentes3

La vue de gauche est-elle identique à la frontière gauche d’un arbre ?

Non. La limite gauche est un chemin : elle part du fils gauche de la racine, va à gauche lorsque c’est possible, sinon à droite, et s’arrête avant une feuille. La vue de gauche prend un nœud par niveau, quelle que soit la branche. Dans le premier exemple, la limite est vide, puisque 8 est une feuille, mais la vue affiche 8, 6 et 1.

Quelle est la complexité temporelle et spatiale de la vue de gauche ?

Les deux solutions parcourent chaque nœud une fois, donc la complexité temporelle est O(n). La file du parcours en largeur contient un niveau entier, soit environ la moitié des nœuds d’un arbre complet. Le parcours en profondeur prioritaire à gauche conserve un appel par niveau, soit O(h) pour h niveaux.

Comment modifier la solution pour obtenir la bonne vue ?

Dans la version en largeur, conserve la dernière valeur de chaque niveau au lieu de la première. Dans la version en profondeur, visite le fils droit avant le fils gauche ; le premier nœud atteint par le parcours à chaque niveau est alors le plus à droite.

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

Test #1

Test #2

Test #3

Argument

root = [3, 8, 5, -1, -1, -1, 6, -1, -1, -1, -1, -1, -1, 1]

Résultat attendu

[3, 8, 6, 1]