Diameter of Binary Tree

+10

On te donne un arbre binaire stocké dans le tableau tree en parcours 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. Retourne le diamètre de l’arbre : le nombre d’arêtes du plus long chemin entre deux nœuds quelconques. Le chemin peut passer par la racine ou rester dans un seul sous-arbre.

Fonction

diameterOfBinaryTree(tree: integer-array) → integer

treeinteger-array: l’arbre binaire dans l’ordre par niveaux, avec -1 pour un emplacement vide
Renvoieinteger: le nombre d’arêtes sur le plus long chemin entre deux nœuds

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 comporte 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 également vides, et la profondeur est au plus de 14.

Exemples

Entrée: tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]
Sortie: 4
Explication: Le chemin 7, 4, 3, 8, 6 (indices 9, 4, 1, 0, 2) contient cinq nœuds reliés par quatre arêtes. Il tourne à la racine : trois arêtes vers le bas du côté gauche et une vers le bas du côté droit.

Entrée: tree = [2, 5, -1, 1, 9, -1, -1, 3, -1, -1, 4]
Sortie: 4
Explication: Le chemin 3, 1, 5, 9, 4 a quatre arêtes et tourne au niveau du 5 à l’index 1. La racine n’a pas de fils droit, donc un chemin passant par la racine ne compte que les trois arêtes qui descendent sur son côté gauche.

Entrée: tree = [6, -1, -1]
Sortie: 0
Explication: Un nœud unique n’a aucune arête. Le chemin le plus long est le nœud lui-même, de longueur 0.

+12 tests cachés à la soumission

Pour aller plus loin

Comment renverrais-tu le chemin lui-même, c’est-à-dire les valeurs des nœuds d’une extrémité du diamètre à l’autre ?

Indices

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

0 sur 3 ouverts

Solution

Le chemin le plus long n’a pas besoin de passer par la racine, donc mesurer les deux côtés de la racine ne suffit pas. Chaque chemin possède un nœud le plus haut, où il passe de la montée à la descente, et le plus long chemin qui tourne à un nœud est la hauteur gauche de ce nœud plus sa hauteur droite. Un seul parcours en post-ordre calcule toutes les hauteurs de bas en haut et vérifie chaque point de bifurcation au passage, en O(n).

Mesurer chaque paire de nœuds

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Tout d’abord, 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, donc son parent se trouve à l’indice (i-1)/2, arrondi à l’entier inférieur. Un emplacement est réel uniquement si son indice se trouve dans le tableau et si la valeur à cet emplacement n’est pas -1. Dans [8, 3, 6, 1, 4, -1, -1, -1, -1, 7], le 7 à l’indice 9 a pour parent l’élément à l’indice 4, et ce 4 a pour parent l’élément à l’indice 1.

Le diamètre est la plus grande distance entre deux nœuds, on peut donc mesurer chaque paire. Pour obtenir la distance entre les indices a et b, remontez vers la racine un pas à la fois jusqu’à ce qu’ils se rejoignent, toujours à partir de l’indice le plus grand. Un indice plus grand ne se trouve jamais à un niveau supérieur, donc cette étape ne dépasse jamais le point de rencontre. Le nombre de pas correspond au nombre d’arêtes. Pour 9 et 2 : le 9 remonte à 4, puis à 1, le 2 remonte à 0, et le 1 remonte à 0. Quatre pas.

C’est correct, mais lent. Le plus grand test est un arbre complet de 16383 nœuds, ce qui donne environ 1.3 × 10^8 paires, et chaque paire nécessite jusqu’à 26 pas. Des milliards de pas pour une seule réponse, c’est bien au-delà de la limite de temps.

Algorithme

Récupérez les indices de tous les nœuds réels.
Pour chaque paire (a, b), définissez edges = 0 et répétez jusqu’à ce que a == b : remplacez l’indice le plus grand par son parent et ajoutez 1 à edges.
Conservez la plus grande valeur de edges que vous voyez et renvoyez-la.

def diameterOfBinaryTree(tree):
    nodes = [i for i, value in enumerate(tree) if value != -1]
    best = 0
    for x in range(len(nodes)):
        for y in range(x + 1, len(nodes)):
            a, b = nodes[x], nodes[y]
            edges = 0
            while a != b:
                # A larger index is never higher up, so climb from it.
                if a > b:
                    a = (a - 1) // 2
                else:
                    b = (b - 1) // 2
                edges += 1
            best = max(best, edges)
    return best

Mesurez les deux hauteurs à chaque nœud

Intuition

Examinez le plus long chemin à partir de son nœud le plus haut, celui où il cesse de monter et commence à descendre. À partir de là, il descend aussi loin que possible du côté gauche et aussi loin que possible du côté droit. Soit height(c) le nombre de nœuds sur le plus long chemin descendant à partir de c, avec 0 pour un emplacement vide. Le plus long chemin qui tourne au nœud i comporte alors height(2*i+1) + height(2*i+2) arêtes, une arête pour chacun de ces nœuds.

Essayez donc chaque nœud comme point de changement de direction et gardez le meilleur résultat. Dans le deuxième exemple, le 5 à l’indice 1 a une hauteur de 2 à gauche (1, 3) et de 2 à droite (9, 4), soit un chemin de quatre arêtes. La racine a une hauteur de 3 à gauche et de 0 à droite, ce qui ne donne que trois arêtes.

Chaque appel à height parcourt un sous-arbre entier, et un nœud est parcouru de nouveau pour chacun de ses ancêtres, donc le travail est de O(n·h). Avec h ≤ 14, c’est assez rapide ici, mais dans un arbre de pointeurs en forme de chaîne, h peut atteindre n et la même idée coûte O(n²). Les appels répétés à height sont le travail superflu que la dernière approche élimine.

Algorithme

Écrivez height(i) : 0 pour un emplacement vide, sinon 1 + max(height(2*i+1), height(2*i+2)).
Pour chaque nœud réel i, calculez height(2*i+1) + height(2*i+2).
Retournez la plus grande de ces sommes.

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

    def height(i):
        # Nodes on the longest downward path from i; an empty spot has 0.
        if i >= n or tree[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    best = 0
    for i in range(n):
        if tree[i] != -1:
            # The longest path that turns at node i goes down both sides.
            best = max(best, height(2 * i + 1) + height(2 * i + 2))
    return best

Un seul parcours en post-ordre des hauteurs

Intuition

La hauteur d’un nœud dépend uniquement de la hauteur de ses deux enfants, et ce sont les deux mêmes nombres dont on a besoin pour vérifier le point de virage. Il suffit donc de les calculer une seule fois, en partant du bas. Un parcours en post-ordre traite les deux enfants avant leur parent. À chaque nœud, tu disposes alors de left et right : mets à jour la réponse avec left + right, puis transmets 1 + max(left, right) au parent.

Dans le premier exemple, la feuille 7 renvoie 1, le 4 situé au-dessus renvoie 2, et le 3 renvoie 3, puisque son autre enfant, 1, a une hauteur de 1. Le 6 renvoie 1. À la racine, left + right = 3 + 1 = 4, la réponse. Le meilleur résultat offert par n’importe quel autre nœud est le 3, avec 1 + 2 = 3.

Chaque nœud est visité une fois, donc le temps d’exécution est O(n), et la récursion est aussi profonde que l’arbre, O(h), soit environ une trame par niveau. La réponse est conservée dans une variable en dehors de la récursion, car la valeur renvoyée par un appel (une hauteur) n’est pas celle recherchée à la fin (la longueur d’un chemin).

Algorithme

Définissez best = 0 et écrivez height(i). Pour une case vide, renvoyez 0.
Calculez left = height(2*i+1) et right = height(2*i+2).
Définissez best comme étant la plus grande valeur entre best et left + right.
Renvoyez 1 + max(left, right).
Appelez height(0) et renvoyez best.

def diameterOfBinaryTree(tree):
    n = len(tree)
    best = 0

    def height(i):
        # Returns the height of node i and updates best on the way back up.
        nonlocal best
        if i >= n or tree[i] == -1:
            return 0
        left = height(2 * i + 1)
        right = height(2 * i + 2)
        best = max(best, left + right)  # the longest path that turns at node i
        return 1 + max(left, right)

    height(0)
    return best

Pièges et cas limites

La plupart des mauvaises réponses comptent la mauvaise chose ou mesurent au mauvais nœud.

Compter les nœuds au lieu des arêtes. Le chemin 7, 4, 3, 8, 6 comporte cinq nœuds et une longueur de 4, et un nœud seul a un diamètre de 0.
Mesurer uniquement les chemins qui passent par la racine. Dans le deuxième exemple, le meilleur chemin passant par la racine a trois arêtes, et la réponse est quatre, avec un virage à l’indice 1.
Renvoyer le diamètre depuis l’appel récursif. Le parent a besoin des hauteurs de ses enfants pour construire des chemins plus longs ; le diamètre doit être stocké dans une variable distincte.
Mélanger deux conventions de hauteur. Avec des hauteurs qui comptent les nœuds et 0 pour une position vide, left + right donne déjà le nombre d’arêtes. Les hauteurs qui comptent les arêtes nécessitent -1 pour une position vide et left + right + 2. Mélanger les deux conventions entraîne une erreur de un ou deux.
Lire au-delà de la fin. Une feuille proche de la fin du tableau peut avoir des indices d’enfants qui dépassent sa dernière entrée. Considérez tout indice au-delà de la fin comme une position vide.
Se tromper dans le décalage en Lua et en R, où les tableaux commencent à 1. Gardez les indices des nœuds à base zéro pour le calcul 2*i+1 et lisez tree[i + 1].

Questions fréquentes4

Quelle est la complexité temporelle du diamètre d’un arbre binaire ?

La solution en parcours post-ordre visite chaque nœud une seule fois : elle s’exécute donc en O(n) et utilise un espace supplémentaire de O(h) pour la récursion, où h est la hauteur. Calculer les hauteurs séparément à chaque nœud coûte O(n·h), ce qui devient O(n²) pour un arbre en forme de chaîne.

Le diamètre d'un arbre binaire passe-t-il toujours par la racine ?

Non. Le chemin le plus long peut se trouver entièrement dans un seul sous-arbre, par exemple lorsque la racine a une branche courte et, de l’autre côté, un sous-arbre profond et touffu. C’est pourquoi tu vérifies left + right à chaque nœud, et pas seulement à la racine.

Le diamètre se compte-t-il en nœuds ou en arêtes ?

Il est ici compté en arêtes, c’est-à-dire les liens entre les nœuds consécutifs du chemin : un seul nœud a donc un diamètre de 0, et deux nœuds connectés ont un diamètre de 1. Certains livres comptent plutôt les nœuds, ce qui donne une unité de plus. Vérifie ce que demande l’énoncé avant d’ajouter ou de retirer le 1.

Comment trouver le diamètre d’un arbre binaire sans récursion ?

Parcourez les nœuds dans un ordre où chaque enfant précède son parent. Une méthode : empilez la racine, dépilez les nœuds dans une liste tout en empilant leurs enfants, puis parcourez cette liste à l’envers. Stockez la hauteur de chaque nœud dans un tableau, lisez les hauteurs des deux enfants à chaque nœud et mettez à jour la réponse avec leur somme. La durée reste O(n).

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

tree = [8, 3, 6, 1, 4, -1, -1, -1, -1, 7]

Attendu

Diameter of Binary Tree

Fonction

Contraintes

Exemples

Indices

Solution

Mesurer chaque paire de nœuds

Mesurez les deux hauteurs à chaque nœud

Un seul parcours en post-ordre des hauteurs

Pièges et cas limites

Questions fréquentes4

Problèmes similaires