Boundary Traversal of Binary Tree

Q: Quelle est la complexité temporelle du parcours de la frontière ?

O(n) . Les deux parcours des bords suivent chacun un chemin, et le parcours des feuilles visite chaque nœud une fois. L’espace supplémentaire est de O(h) pour la récursion ou la pile.

MoyenParcours d’arbre

+10

Le tableau root contient un arbre binaire en ordre par niveaux : la racine à l’indice 0, les enfants de l’indice i aux indices 2i+1 (à gauche) et 2i+2 (à droite), -1 pour un emplacement vide, et éventuellement des entrées -1 supplémentaires à la fin. Une feuille est un nœud sans enfants.

Renvoie le contour dans le sens antihoraire à partir de la racine :

La racine.
Le bord gauche, de haut en bas : à partir de l’enfant gauche de la racine, passe à l’enfant gauche s’il existe, sinon à l’enfant droit. Arrête-toi avant une feuille.
Toutes les feuilles, de gauche à droite.
Le bord droit, de bas en haut : le miroir du bord gauche, à partir de l’enfant droit de la racine.

Aucun nœud n’est répertorié deux fois ; un arbre à un seul nœud ne donne donc que sa racine.

Fonction

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

rootinteger-array: l’arbre binaire dans l’ordre par niveau, avec -1 pour une place vide
Renvoieinteger-array: les valeurs aux limites, dans le sens antihoraire à partir de la racine

Contraintes

1 ≤ root.length ≤ 32767
Chaque root[i] vaut -1 ou une valeur telle que 0 ≤ root[i] ≤ 10⁵.
root[0] n'est jamais -1, donc l'arbre a 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.
Les valeurs des nœuds sont distinctes.

Exemples

Entrée: root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
Sortie: [7, 3, 1, 4, 6, 8, 9]
Explication: Après la racine 7, la frontière gauche est 3 : son enfant 1 est une feuille. Les feuilles sont 1, 4, 6, 8. La frontière droite est 9, au-dessus de la feuille 8.

Entrée: root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
Sortie: [10, 4, 6, 5, 8]
Explication: 4 n’a pas d’enfant gauche, donc la limite gauche se déplace vers 6, puis s’arrête à la feuille 5. Les feuilles 5, 8 suivent. La racine n’a pas d’enfant droit.

Pour aller plus loin

Comment énuméreriez-vous la frontière dans le sens horaire : la racine, le bord droit de haut en bas, les feuilles de droite à gauche, puis le bord gauche de bas en haut ?

Indices

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

0 sur 3 ouverts

Solution

La réponse réunit quatre parties : la racine, un chemin le long du bord gauche, les feuilles de gauche à droite et un chemin le long du bord droit lu à l’envers. Aux jonctions, une feuille terminant un bord et une racine qui est une feuille doivent chacune être répertoriées une seule fois.

Parcourez les trois parties séparément

Intuition

Chaque arête correspond à un chemin : à partir de l’enfant de la racine, énumérez les nœuds jusqu’à ce que le suivant soit une feuille, que la partie consacrée aux feuilles énumère à la place. Un parcours préfixe qui va à gauche avant d’aller à droite rencontre les feuilles de gauche à droite, car tous les nœuds du sous-arbre gauche se trouvent à gauche du sous-arbre droit, quelle que soit leur profondeur. Collectez l’arête droite de haut en bas, puis ajoutez-la à l’envers.

Chaque arête suit un seul chemin et le parcours des feuilles visite chaque nœud une fois : temps O(n), avec une récursion de h niveaux de profondeur.

Algorithme

Commencez par la racine ; si c’est une feuille, retournez-la.
À partir de l’indice 1, tant que le nœud existe et n’est pas une feuille, ajoutez-le et passez à son enfant gauche, ou à son enfant droit s’il n’en a pas à gauche.
Parcourez en pré-ordre, en commençant par la gauche, à partir des indices 1 et 2, en ajoutant chaque feuille.
À partir de l’indice 2, faites la même chose qu’à l’étape 2 en privilégiant les enfants droits, et collectez les nœuds.
Ajoutez les nœuds collectés dans l’ordre inverse.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    def is_leaf(i):
        return not real(2 * i + 1) and not real(2 * i + 2)

    result = [root[0]]
    if is_leaf(0):
        return result

    # 1. The left boundary, top-down, stopping before its leaf.
    i = 1
    while real(i) and not is_leaf(i):
        result.append(root[i])
        i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2

    # 2. Every leaf: a pre-order walk meets them from left to right.
    def add_leaves(i):
        if not real(i):
            return
        if is_leaf(i):
            result.append(root[i])
            return
        add_leaves(2 * i + 1)
        add_leaves(2 * i + 2)

    add_leaves(1)
    add_leaves(2)

    # 3. The right boundary, collected top-down and added bottom-up.
    right = []
    i = 2
    while real(i) and not is_leaf(i):
        right.append(root[i])
        i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
    result.extend(reversed(right))
    return result

Un parcours en préordre avec des indicateurs d’arête

Intuition

Fusionnez les parcours en un seul parcours en préordre à l'aide d'une pile, en attribuant un indicateur à chaque nœud : 1 sur le bord gauche, 2 sur le bord droit, 0 à l'intérieur. Les enfants de la racine commencent avec 1 et 2. Un nœud de bord transmet son indicateur à l'enfant situé de son côté, ou à son unique enfant ; chaque autre enfant reçoit 0. Dans le deuxième exemple, le 1 se transmet de 4 à 6, puis à 5.

À mesure que les nœuds sortent de la pile, ajoutez chaque feuille et chaque nœud qui n'est pas une feuille et qui porte l'indicateur 1 ; rassemblez les nœuds qui ne sont pas des feuilles et qui portent l'indicateur 2, puis ajoutez-les à la fin dans l'ordre inverse. Le parcours en préordre atteint chaque nœud du bord gauche avant toute feuille, car le bord tourne vers la droite uniquement là où rien ne se trouve à sa gauche.

Algorithme

Commence par la racine. Empile son enfant droit avec le drapeau 2, puis son enfant gauche avec le drapeau 1.
Dépile un nœud. Ajoute-le s’il s’agit d’une feuille ou s’il a le drapeau 1 ; ajoute un nœud interne avec le drapeau 2 à la liste de droite.
Empile son enfant droit, puis son enfant gauche, chacun avec le drapeau que la règle lui attribue.
Lorsque la pile est vide, ajoute la liste de droite dans l’ordre inverse.

def boundaryTraversal(root):
    n = len(root)

    def real(i):
        return i < n and root[i] != -1

    result = [root[0]]
    right = []  # the right boundary, top-down; it goes on the end reversed
    # Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
    stack = []
    if real(2):
        stack.append((2, 2))
    if real(1):
        stack.append((1, 1))
    while stack:
        i, edge = stack.pop()
        has_left, has_right = real(2 * i + 1), real(2 * i + 2)
        if not has_left and not has_right:
            result.append(root[i])  # a leaf; pre-order meets them left to right
        elif edge == 1:
            result.append(root[i])  # the left boundary, top-down
        elif edge == 2:
            right.append(root[i])
        # An edge passes to the child on its own side, or to an only child.
        # The right child goes on the stack first, so the left one comes out first.
        if has_right:
            stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
        if has_left:
            stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
    result.extend(reversed(right))
    return result

Pièges et cas limites

Énumérer un nœud deux fois. Un parcours des arêtes qui ne s’arrête pas avant sa feuille énumère 1 deux fois dans l’exemple 1, et un arbre à un seul nœud ne doit pas énumérer à nouveau sa racine comme feuille.
Prendre le premier nœud de chaque niveau comme limite gauche. Si le fils gauche de la racine est une feuille et que le sous-arbre droit est plus profond, les niveaux plus profonds commencent par des nœuds du sous-arbre droit, alors que la limite gauche est vide.
Suivre uniquement les fils gauches. Dans l’exemple 2, la limite doit aller de 4 à son fils droit 6.
Collecter les feuilles niveau par niveau. L’exemple 1 donne alors 1, 8, 4, 6.
En Lua et en R, conserver les index des nœuds basés sur 0 pour le calcul 2i+1 et lire root[i + 1].

Questions fréquentes3

Qu’est-ce que le parcours de la frontière d’un arbre binaire ?

Elle énumère le contour de l’arbre dans le sens antihoraire : la racine, le bord gauche de haut en bas, les feuilles de gauche à droite, puis le bord droit de bas en haut. Les bords excluent leurs feuilles, de sorte qu’aucun nœud n’apparaît deux fois.

Quelle est la complexité temporelle du parcours de la frontière ?

O(n). Les deux parcours des bords suivent chacun un chemin, et le parcours des feuilles visite chaque nœud une fois. L’espace supplémentaire est de O(h) pour la récursion ou la pile.

La limite gauche suit-elle toujours les enfants de gauche ?

Non. Il se déplace vers l’enfant gauche lorsqu’il y en a un, et vers l’enfant droit dans le cas contraire : le chemin le plus extérieur que tu vois depuis la gauche. Si la racine n’a pas d’enfant gauche, la frontière gauche est vide.

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

Test #1

Test #2

Test #3

Argument

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

Résultat attendu

[7, 3, 1, 4, 6, 8, 9]