Maximum Depth of Binary Tree
On vous donne un arbre binaire stocké dans le tableau tree en ordre par niveau. 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. Renvoyez la profondeur maximale de l’arbre : le nombre de nœuds sur le plus long chemin de la racine jusqu’à une feuille.
Fonction
- 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-1ou une valeur telle que0 ≤ tree[i] ≤ 1000. tree[0]n’est jamais-1, donc l’arbre contient au moins un nœud.- L’array peut se terminer par des entrées
-1supplé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 = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
- Sortie
- 4
- Explication
- Le chemin le plus long est
5,8,3,6(indices0,1,4,9), qui contient 4 nœuds. Le chemin passant par1s’arrête après 2 nœuds.
- Entrée
- tree = [7, -1, -1]
- Sortie
- 1
- Explication
- Les deux entrées
-1correspondent aux emplacements vides des enfants de la racine. La racine seule constitue un chemin d’un nœud, donc la profondeur est de1, et non de0.
- Entrée
- tree = [2, -1, 9, -1, -1, -1, 4]
- Sortie
- 3
- Explication
- La racine
2n’a pas d’enfant gauche. Son enfant droit9à l’index2a4à l’index6comme enfant droit, un chemin de 3 nœuds.
+13 tests cachés à la soumission
Pour aller plus loin
Comment renverrais-tu les valeurs d’un plus long chemin de la racine à une feuille, et pas seulement sa longueur ? Si plusieurs chemins sont à égalité, lequel renverrais-tu, et comment le préciserais-tu dans le contrat ?
Indices
Ouvrez-les un par un. Chacun en dévoile un peu plus.
Pense à la racine. Si tu connaissais la profondeur de son sous-arbre gauche et la profondeur de son sous-arbre droit, quelle serait la profondeur de l’arbre entier ?
C’est
1pour la racine plus la plus grande des profondeurs des deux sous-arbres, et un emplacement vide a une profondeur de0. La même règle s’applique à chaque nœud, donc un parcours qui connaît la profondeur de chaque nœud peut trouver la réponse.Conservez une pile de paires, un indice de nœud et sa profondeur, en commençant par la racine à la profondeur 1. Dépilez une paire, mémorisez la profondeur maximale observée et empilez chaque enfant à l’indice
2*i+1et2*i+2s’il se trouve dans le tableau et n’est pas-1, avec une profondeur augmentée de un.
Solution
La profondeur est déterminée par la branche la plus longue, et tu ne peux pas savoir laquelle c’est sans examiner chaque nœud. La tâche consiste donc à parcourir l’arbre en entier en sachant à quelle profondeur tu te trouves à chaque nœud. La récursion, un parcours en largeur niveau par niveau et un parcours en profondeur avec ta propre pile permettent tous de le faire en un seul passage ; ils diffèrent dans la façon dont ils suivent leur position.
Récursion sur les deux sous-arbres
Intuition
Tout d’abord, voyons 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. Un enfant n’existe que si son indice se trouve dans le tableau et que la valeur à cet emplacement n’est pas -1. Dans [5, 8, 1, -1, 3, -1, -1, -1, -1, 6], la racine 5 a des enfants aux indices 1 et 2, le 8 à l’indice 1 a un emplacement vide à gauche à l’indice 3 et le 3 à l’indice 4 à droite, et ce 3 a le 6 à l’indice 9 en dessous de lui.
Voyons maintenant l’idée. Le chemin le plus profond passant par un nœud descend dans le plus profond de ses deux sous-arbres. Ainsi, la profondeur du sous-arbre à l’indice i est égale à 1 pour le nœud lui-même, 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 obtient 1 + max(0, 0) = 1, et les valeurs remontent jusqu’à la racine.
Chaque nœud est visité une fois, donc la complexité temporelle est O(n). La pile d’appels contient une trame par niveau du chemin actuel, soit O(h), où h est la profondeur, au plus 14 ici. Cette limite rend la récursion sûre dans ce problème. Sur un arbre basé sur des pointeurs et formé comme une longue chaîne, le même code atteindrait la limite de récursion, qui est de 1000 trames dans Python.
Algorithme
- Écrivez
depth(i): siidépasse la fin du tableau ou sitree[i]vaut-1, renvoyez0. - 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 de l’arbre : tu peux donc compter les niveaux au lieu de suivre les chemins. Une file visite les nœuds dans l’ordre des niveaux : commence par y placer la racine, puis chaque fois que tu retires un nœud, ajoute ses enfants réels à la fin.
Pour compter les niveaux, traite la file par lots. Avant chaque lot, regarde combien de nœuds la file contient. Ce sont exactement les nœuds d’un même niveau, car les enfants que tu ajoutes pendant le lot sont placés derrière eux. Retire ce nombre de nœuds, ajoute leurs enfants à la file, puis ajoute 1 à la profondeur. Lorsque la file est vide, la profondeur correspond au nombre de lots. Dans le premier exemple, les lots sont [5], [8, 1], [3] et [6], donc la réponse est 4.
Chaque nœud entre dans la file et en sort une fois : temps O(n). La file contient un seul niveau à la fois : espace O(w) pour le niveau le plus large w. Dans un arbre complet, le niveau inférieur contient environ la moitié des nœuds : 8192 sur 16383 à la profondeur 14.
Algorithme
- Placez l’index racine
0dans une file d’attente et définissezdepth = 0. - Tant que la file d’attente n’est pas vide, ajoutez
1àdepthet lisez la taille de la file. - Retirez ce nombre d’index. Pour chacun d’eux, ajoutez à la file les index enfants
2*i+1et2*i+2qui se trouvent dans le tableau et ne sont pas égaux à-1. - Lorsque la file d’attente est vide, renvoyez
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 depthRecherche en profondeur avec une pile explicite
Intuition
Tu peux suivre des chemins, comme le fait la récursion, sans effectuer le moindre appel récursif. Garde ta propre pile et stocke chaque nœud avec sa profondeur, puisque rien d’autre ne se souvient de sa distance par rapport à la racine. Commence par la paire (0, 1) : la racine, à la profondeur 1.
Dépile une paire, compare sa profondeur à la meilleure profondeur observée jusqu’ici, puis empile chaque enfant existant avec depth + 1. Chaque nœud de l’arbre est empilé exactement 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 à l’index 9 est empilé sous la forme (9, 4), et aucune paire ne va plus en profondeur.
La complexité temporelle est O(n). La pile contient les frères en attente le long du chemin actuel, au plus environ un par niveau ; l’espace utilisé est donc O(h), comme avec la récursion, mais sans risque de débordement de la pile d’appels. C’est la version à privilégier lorsqu’un arbre peut être profond, et elle s’applique sans modification aux arbres basés sur des pointeurs.
Algorithme
- Empilez
(0, 1)et définissezbest = 0. - Dépilez une paire
(i, depth)et définissezbestcomme étant la plus grande valeur entrebestetdepth. - Pour chaque indice enfant
2*i+1et2*i+2qui se trouve dans le tableau et n’est pas-1, empilez-le avecdepth + 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
La plupart des mauvaises réponses à ce problème comportent une erreur de décalage d'une unité ou viennent du fait qu'on traite un emplacement vide comme un nœud.
- Compter les arêtes au lieu des nœuds. Un seul nœud a ici une profondeur de
1; renvoyer0pour celui-ci, ou3pour une chaîne de 4 nœuds, revient à compter une unité de moins. - Oublier la vérification des limites. Une feuille proche de la fin du tableau peut avoir des indices d'enfants qui dépassent son dernier élément, car le tableau peut s'arrêter juste après le dernier nœud. Vérifie
child < navant de liretree[child]. - Déduire la profondeur de la longueur du tableau. Le tableau peut contenir des éléments
-1supplémentaires à la fin, donc sa longueur peut correspondre à un niveau plus profond que celui de n'importe quel nœud réel. - Traiter
-1comme une valeur. Il indique un nœud manquant, donc il ne faut ni l'empiler, ni le mettre dans la file, ni le compter. - Supposer que l'arbre est équilibré. La réponse dépend de la branche la plus longue, comme dans une chaîne de 14 nœuds vers la gauche où chaque emplacement à droite est vide.
- Lire la taille de la file à l'intérieur de la boucle dans la version en parcours en largeur. La taille change lorsque des enfants sont ajoutés : sauvegarde-la donc avant le début du traitement du lot.
- Confondre le décalage en Lua et en R, où les tableaux commencent à l'indice 1. Garde les indices des nœuds à partir de 0 pour le calcul
2*i+1et listree[i + 1].
Questions fréquentes4
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 exploré, où h est la profondeur. La version en largeur utilise O(w) pour le niveau le plus large, qui peut contenir 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 donnent la bonne réponse en O(n). La recherche en profondeur est plus courte à écrire et utilise une 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 mémoire proportionnelle au niveau le plus large, ce qui convient aux arbres profonds et étroits. Pour la profondeur minimale, le BFS a l’avantage, car il peut s’arrêter à la première feuille qu’il rencontre.
Comment trouver la profondeur maximale d’un arbre binaire sans récursion ?
Utilisez une pile explicite de paires : un nœud et sa profondeur. Commencez avec la racine à la profondeur 1, dépilez une paire, enregistrez sa profondeur et empilez chaque enfant avec une profondeur augmentée de un. La plus grande profondeur dépilée est la réponse. Une file traitée niveau par niveau fonctionne aussi, en comptant un niveau à la fois.
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’à celui-ci, et la hauteur d’un nœud compte les étapes depuis celui-ci jusqu’à sa feuille la plus profonde. La profondeur maximale de l’arbre et la hauteur de la racine correspondent au même nombre. Ce problème compte les nœuds : un nœud seul a donc une profondeur de 1 ; certains livres comptent plutôt les arêtes, ce qui donne une unité de moins.
Problèmes similaires
Des problèmes qui reposent sur les mêmes idées. En résoudre deux ou trois, c’est ce qui ancre un schéma.
Python
def maxDepth(tree):
# Écrivez le code iciCas 1
Cas 2
Cas 3
Entrée
tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Attendu
4