Maximum Depth of Binary Tree

Q: Quelle est la complexité temporelle de la profondeur maximale d’un arbre binaire ?

Chaque approche visite chaque nœud une fois, donc la complexité temporelle est O(n) . Les versions en profondeur utilisent un espace supplémentaire de O(h) pour le chemin courant, où h est la profondeur. La version en largeur utilise O(w) pour le niveau le plus large, soit environ la moitié des nœuds d’un arbre complet.

Q: Faut-il utiliser DFS ou BFS pour trouver la profondeur maximale d’un arbre binaire ?

Les deux s’exécutent en temps O(n) . La recherche en profondeur est plus courte à écrire et utilise une quantité de mémoire proportionnelle à la profondeur, ce qui convient aux arbres larges et peu profonds. La recherche en largeur compte directement les niveaux et utilise une quantité de mémoire proportionnelle au niveau le plus large, ce qui convient aux arbres profonds et étroits. Pour trouver la profondeur minimale, la recherche en largeur est plus efficace, car elle peut s’arrêter à la première feuille.

Q: Quelle est la différence entre la profondeur et la hauteur d’un arbre binaire ?

La profondeur d’un nœud compte les étapes depuis la racine jusqu’à lui ; la hauteur compte les étapes depuis ce nœud jusqu’à sa feuille la plus profonde. La profondeur maximale de l’arbre est égale à la hauteur de la racine. Ce problème compte les nœuds : un nœud seul a donc une profondeur de 1 ; compter les arêtes donne une valeur inférieure de un.

FacileParcours d’arbre

+10

Vous obtenez un arbre binaire stocké dans le tableau tree dans l’ordre 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 un emplacement vide, et le tableau peut se terminer par des entrées -1 supplémentaires. Renvoyez la profondeur maximale de l’arbre : le nombre de nœuds sur le plus long chemin de la racine jusqu’à une feuille.

Fonction

maxDepth(tree: integer-array) → integer

treeinteger-array: l’arbre binaire dans l’ordre par niveaux, avec -1 pour une position vide
Renvoieinteger: le nombre de nœuds sur le plus long chemin de la racine à une feuille

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 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 au plus 14.

Exemples

Entrée: tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Sortie: 4
Explication: Le chemin le plus long est 5, 8, 3, 6 (indices 0, 1, 4, 9), qui contient 4 nœuds. Le chemin passant par 1 s’arrête après 2 nœuds.

Entrée: tree = [7, -1, -1]
Sortie: 1
Explication: Les deux entrées -1 correspondent aux emplacements vides des enfants de la racine. La racine seule forme un chemin d’un nœud, donc la profondeur est 1, et non 0.

Entrée: tree = [2, -1, 9, -1, -1, -1, 4]
Sortie: 3
Explication: La racine 2 n’a pas de fils gauche. Son fils droit 9 à l’index 2 a 4 à l’index 6 comme fils droit, soit un chemin de 3 nœuds.

Pour aller plus loin

Comment renverrais-tu les valeurs d’un plus long chemin de la racine à une feuille, ainsi que sa longueur ? Si plusieurs chemins sont ex æquo, lequel renverrais-tu ?

Indices

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

0 sur 3 ouverts

Solution

La profondeur est déterminée par la branche la plus longue, et tu ne peux pas savoir laquelle c’est sans visiter chaque nœud. Tu as donc besoin d’un parcours complet qui connaît la profondeur à chaque nœud. La récursion, une recherche en largeur par niveaux et une recherche en profondeur avec ta propre pile permettent toutes de le faire en un seul passage.

Récursion sur les deux sous-arbres

Intuition

Un emplacement enfant est réel lorsque son indice se trouve dans le tableau et que sa valeur n’est pas -1. Le chemin le plus profond à travers un nœud descend dans son sous-arbre le plus profond, donc la profondeur à l’indice i est égale à 1 pour le nœud, plus la plus grande des profondeurs aux indices 2*i+1 et 2*i+2. Un emplacement vide a une profondeur de 0, ce qui met fin à la récursion. Une feuille a une profondeur de 1 + max(0, 0) = 1, et les valeurs remontent jusqu’à la racine.

Chaque nœud est visité une fois. La pile d’appels contient une trame par niveau du chemin actuel, O(h), au plus 14 ici.

Algorithme

Écrivez depth(i) : si i dépasse la fin du tableau ou si tree[i] vaut -1, renvoyez 0.
Sinon, renvoyez 1 + max(depth(2*i+1), depth(2*i+2)).
Renvoyez depth(0).

def maxDepth(tree):
    def depth(i):
        # An index past the end or a -1 is an empty spot: depth 0.
        if i >= len(tree) or tree[i] == -1:
            return 0
        return 1 + max(depth(2 * i + 1), depth(2 * i + 2))

    return depth(0)

Parcours en largeur, niveau par niveau

Intuition

La profondeur maximale correspond au nombre de niveaux : tu peux donc compter les niveaux au lieu de suivre les chemins. Une file visite les nœuds dans l’ordre des niveaux. Avant chaque lot, lis la taille de la file : ces nœuds correspondent exactement à un niveau, car les enfants que tu ajoutes pendant le lot sont placés derrière eux. Chaque lot ajoute 1 à la profondeur. Dans le premier exemple, les lots sont [5], [8, 1], [3] et [6] : la réponse est donc 4.

La file contient un seul niveau à la fois, soit O(w) pour le niveau le plus large. Dans un arbre complet de profondeur 14, cela représente 8192 des 16383 nœuds.

Algorithme

Place l’indice racine 0 dans une file et définis depth = 0.
Tant que la file n’est pas vide, ajoute 1 à depth et lis la taille de la file.
Retire autant d’indices. Pour chacun, ajoute à la file les indices des enfants 2*i+1 et 2*i+2 qui se trouvent dans le tableau et ne sont pas -1.
Lorsque la file est vide, renvoie depth.

from collections import deque


def maxDepth(tree):
    n = len(tree)
    queue = deque([0])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):  # exactly the nodes of this level
            i = queue.popleft()
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
    return depth

Recherche en profondeur avec une pile explicite

Intuition

Garde ta propre pile de paires, un indice de nœud et sa profondeur, car rien d’autre ne mémorise la profondeur d’un nœud. Commence par (0, 1), la racine à la profondeur 1. Chaque nœud est empilé une fois, avec la longueur du chemin qui y mène ; la plus grande profondeur que tu dépiles est donc la réponse. Dans le premier exemple, le 6 est empilé sous la forme (9, 4).

La pile contient environ un frère en attente par niveau, O(h), sans pile d’appels susceptible de déborder. Le même code fonctionne sur un arbre basé sur des pointeurs, quelle que soit sa profondeur.

Algorithme

Empilez (0, 1) et définissez best = 0.
Dépilez une paire (i, depth) et définissez best comme étant la plus grande valeur entre best et depth.
Pour chaque indice enfant 2*i+1 et 2*i+2 qui se trouve dans le tableau et n'est pas -1, empilez-le avec depth + 1.
Répétez jusqu'à ce que la pile soit vide, puis renvoyez best.

def maxDepth(tree):
    n = len(tree)
    best = 0
    stack = [(0, 1)]  # (node index, depth of that node); the root is never empty
    while stack:
        i, depth = stack.pop()
        best = max(best, depth)
        for child in (2 * i + 1, 2 * i + 2):
            if child < n and tree[child] != -1:
                stack.append((child, depth + 1))
    return best

Pièges et cas limites

Compter les arêtes plutôt que les nœuds. [7, -1, -1] a une profondeur de 1, et non de 0.
Omettre la vérification des limites. Dans le premier exemple, le 6 à l’index 9 a pour index d’enfants 19 et 20, qui dépassent la fin du tableau. Vérifie child < n avant de lire tree[child].
Calculer la profondeur à partir de la longueur du tableau. Les entrées -1 finales atteignent un niveau sans nœud : [7, -1, -1] a une longueur de 3, mais une profondeur de 1.
Lire la taille de la file à l’intérieur de la boucle de traitement par lots. Les enfants ajoutés pendant le traitement modifient cette taille, alors enregistre-la d’abord.
Confondre le décalage en Lua et en R, où les tableaux commencent à 1. Garde les index des nœuds à base 0 pour 2*i+1 et lis tree[i + 1].

Questions fréquentes3

Quelle est la complexité temporelle de la profondeur maximale d’un arbre binaire ?

Chaque approche visite chaque nœud une fois, donc la complexité temporelle est O(n). Les versions en profondeur utilisent un espace supplémentaire de O(h) pour le chemin courant, où h est la profondeur. La version en largeur utilise O(w) pour le niveau le plus large, soit environ la moitié des nœuds d’un arbre complet.

Faut-il utiliser DFS ou BFS pour trouver la profondeur maximale d’un arbre binaire ?

Les deux s’exécutent en temps O(n). La recherche en profondeur est plus courte à écrire et utilise une quantité de mémoire proportionnelle à la profondeur, ce qui convient aux arbres larges et peu profonds. La recherche en largeur compte directement les niveaux et utilise une quantité de mémoire proportionnelle au niveau le plus large, ce qui convient aux arbres profonds et étroits. Pour trouver la profondeur minimale, la recherche en largeur est plus efficace, car elle peut s’arrêter à la première feuille.

Quelle est la différence entre la profondeur et la hauteur d’un arbre binaire ?

La profondeur d’un nœud compte les étapes depuis la racine jusqu’à lui ; la hauteur compte les étapes depuis ce nœud jusqu’à sa feuille la plus profonde. La profondeur maximale de l’arbre est égale à la hauteur de la racine. Ce problème compte les nœuds : un nœud seul a donc une profondeur de 1 ; compter les arêtes donne une valeur inférieure de un.

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

Test #1

Test #2

Test #3

Argument

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

Résultat attendu

Maximum Depth of Binary Tree

Fonction

Contraintes

Exemples

Indices

Solution

Récursion sur les deux sous-arbres

Parcours en largeur, niveau par niveau

Recherche en profondeur avec une pile explicite

Pièges et cas limites

Questions fréquentes3

Problèmes similaires