Diamètre, hauteur et arbres équilibrés
Calculez le diamètre et la hauteur d’un arbre en un seul parcours DFS grâce à une fonction auxiliaire qui renvoie les deux valeurs, puis vérifiez si l’arbre est équilibré en hauteur.
Diamètre, hauteur et arbres équilibrés est une leçon DSA Interview Prep gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage DSA Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours DSA Interview Prep comprend 4 leçons au total.
Hauteur d’un arbre binaire
La hauteur (ou profondeur maximale) d’un arbre binaire est la longueur du plus long chemin entre la racine et une feuille quelconque. Elle se calcule récursivement : la hauteur d’un nœud est 1 + max(height(left), height(right)), avec un cas de base égal à 0 pour les nœuds nuls. Ce calcul en postordre est fondamental : la hauteur constitue la base du diamètre, de la vérification de l’équilibre et des rotations d’un arbre AVL.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def height(root):
if not root:
return 0
return 1 + max(height(root.left), height(root.right))
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)
print(height(root)) # 4Diamètre : le plus long chemin
Le diamètre d’un arbre binaire est la longueur du plus long chemin entre deux nœuds quelconques (ce chemin peut passer par la racine ou non). La longueur du chemin se mesure en arêtes. Pour un nœud donné, le diamètre passant par ce nœud vaut height(left) + height(right). Le diamètre global est la plus grande de ces valeurs parmi tous les nœuds de l’arbre.
def diameter_of_binary_tree(root):
max_diameter = [0] # use list to allow closure mutation
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Diameter through this node
max_diameter[0] = max(max_diameter[0], left_h + right_h)
return 1 + max(left_h, right_h) # height for parent
dfs(root)
return max_diameter[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_of_binary_tree(root)) # 3Un seul passage de DFS pour le diamètre
L’approche naïve appelle height() pour chaque nœud, ce qui donne une complexité O(n²) pour un arbre équilibré. La solution optimale calcule la hauteur et met à jour le diamètre en un seul passage de DFS. L’idée essentielle est que la fonction récursive dfs() remplit simultanément deux rôles : elle renvoie la hauteur au parent tout en mettant à jour un diamètre maximal global comme effet secondaire. Ce schéma de postordre à double fonction apparaît dans de nombreux problèmes sur les arbres.
# O(n^2) NAIVE: recomputes height for every node
def diameter_naive(root):
if not root:
return 0
through_root = height(root.left) + height(root.right)
in_left = diameter_naive(root.left)
in_right = diameter_naive(root.right)
return max(through_root, in_left, in_right)
# O(n) OPTIMAL: single DFS pass (shown in previous scene)
# The naive version is O(n^2) because height() is O(n)
# and it is called for every node.
print('Naive: O(n^2) | Optimal single-pass: O(n)')Vérifier l’équilibre d’un arbre binaire
Un arbre binaire est équilibré en hauteur si les hauteurs des sous-arbres gauche et droit de chaque nœud diffèrent d’au plus un. L’approche par force brute appelle height() pour chaque nœud, ce qui donne une complexité O(n²). L’approche optimale utilise la même astuce du passage unique : renvoyez -1 comme valeur sentinelle pour signaler un arbre « déséquilibré » et propagez cette valeur vers le haut, en arrêtant rapidement le parcours dès qu’un nœud déséquilibré est trouvé.
def is_balanced(root):
def check(node):
if not node:
return 0
left = check(node.left)
if left == -1:
return -1 # propagate early exit
right = check(node.right)
if right == -1:
return -1
if abs(left - right) > 1:
return -1 # unbalanced here
return 1 + max(left, right) # height if balanced
return check(root) != -1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.left.left = TreeNode(5) # too deep on left
print(is_balanced(root)) # FalseLe schéma de la valeur de retour sentinelle
Renvoyer une valeur sentinelle (-1 pour un arbre déséquilibré ou un tuple spécial) est un schéma courant lorsqu’une fonction auxiliaire de DFS doit transmettre deux types d’informations : le résultat calculé et l’indication qu’une contrainte a été enfreinte. Au lieu de lever des exceptions ou d’utiliser des indicateurs globaux, encodez l’erreur dans le type de retour. Cette approche est claire, évite l’état global et se compose naturellement avec d’autres fonctions récursives auxiliaires.
# General pattern: return (is_valid, computed_value)
def balanced_height(node):
if not node:
return True, 0
left_ok, left_h = balanced_height(node.left)
if not left_ok:
return False, 0 # short-circuit
right_ok, right_h = balanced_height(node.right)
if not right_ok:
return False, 0
balanced = abs(left_h - right_h) <= 1
return balanced, 1 + max(left_h, right_h)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
ok, h = balanced_height(root)
print(ok, h) # True 2Diamètre mesuré en nœuds ou en arêtes
Soyez attentif à l’énoncé du problème : LeetCode n°543 mesure le diamètre en arêtes, tandis que certains problèmes le mesurent en nœuds. Si vous devez compter les nœuds, le diamètre passant par un nœud est height(left) + height(right) + 1 (ajoutez 1 pour le nœud lui-même). Si vous devez compter les arêtes, omettez le +1. Clarifiez toujours ce point avec votre intervieweur avant de coder.
def diameter_in_nodes(root):
max_path = [0]
def dfs(node):
if not node:
return 0
left_h = dfs(node.left)
right_h = dfs(node.right)
# Path through this node in NODE count
nodes_through = left_h + right_h + 1
max_path[0] = max(max_path[0], nodes_through)
return 1 + max(left_h, right_h)
dfs(root)
return max_path[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(diameter_in_nodes(root)) # 4 nodes: 4-2-1-3 or 5-2-1-3Somme d’un chemin : de la racine à une feuille quelconque
Le problème de la somme d’un chemin demande si la somme d’un chemin quelconque allant de la racine à une feuille est égale à une valeur cible. Utilisez DFS et soustrayez la valeur du nœud courant de la cible à mesure que vous descendez. À une feuille, vérifiez si la cible restante est égale à la valeur de la feuille. Il s’agit d’un DFS en préordre dans lequel vous transmettez la somme restante comme paramètre — un exemple classique de récursion descendante.
def has_path_sum(root, target):
if not root:
return False
# Leaf node: check if we've exactly hit the target
if not root.left and not root.right:
return root.val == target
remaining = target - root.val
return (has_path_sum(root.left, remaining) or
has_path_sum(root.right, remaining))
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.left = TreeNode(7)
root.left.left.right = TreeNode(2)
print(has_path_sum(root, 22)) # True: 5+4+11+2=22Somme maximale d’un chemin (variante difficile)
La somme maximale d’un chemin (LeetCode n°124) est nettement plus difficile : le chemin peut commencer et se terminer à n’importe quel nœud, et pas uniquement aller de la racine à une feuille ; de plus, les valeurs peuvent être négatives. Pour chaque nœud, envisagez quatre possibilités : le nœud seul, le nœud avec la branche gauche, le nœud avec la branche droite, ou le nœud avec les deux branches. Seules les trois premières peuvent être prolongées vers le parent ; la quatrième constitue une valeur candidate finale pour le maximum global.
def max_path_sum(root):
max_sum = [float('-inf')]
def gain(node):
if not node:
return 0
# Only take positive contributions
left = max(gain(node.left), 0)
right = max(gain(node.right), 0)
# Best path through this node (can't go both ways upward)
max_sum[0] = max(max_sum[0], node.val + left + right)
# Return the best single-branch gain for parent
return node.val + max(left, right)
gain(root)
return max_sum[0]
root = TreeNode(-10)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(max_path_sum(root)) # 42: 15+20+7Arbres AVL et équilibrage automatique
Un arbre AVL est un BST qui maintient la propriété d’équilibre en hauteur en effectuant des rotations après les opérations d’insertion et de suppression. Chaque nœud stocke un facteur d’équilibre (hauteur du sous-arbre droit - hauteur du sous-arbre gauche), qui doit rester dans {-1, 0, 1}. Lorsqu’une violation se produit, une rotation simple ou double rétablit l’équilibre en temps O(1), ce qui maintient la hauteur globale à O(log n) et garantit que toutes les opérations s’effectuent en O(log n).
# Balance factor = height(right) - height(left)
# AVL invariant: balance factor in {-1, 0, 1} for every node
# Four violation types and their fixes:
# LL (left-heavy left child): single right rotation
# RR (right-heavy right child): single left rotation
# LR (right-heavy left child): left rotate child, then right rotate root
# RL (left-heavy right child): right rotate child, then left rotate root
# Knowing this is enough for interviews; you rarely implement
# full AVL in an interview but must discuss the concept.
print('AVL maintains O(log n) height via rotations')Vérifier la symétrie d’un arbre
Un arbre binaire est symétrique s’il est l’image miroir de lui-même. Vérifiez-le récursivement : l’arbre est symétrique si, pour chaque paire de nœuds correspondants de part et d’autre de l’axe, leurs valeurs sont égales et leurs sous-arbres sont en miroir. Définissez une fonction auxiliaire is_mirror(left, right) qui vérifie les cas suivants : les deux nœuds sont nuls (correct), un seul est nul (incorrect), les valeurs sont égales et les sous-arbres intérieur et extérieur sont en miroir.
def is_symmetric(root):
def is_mirror(left, right):
if not left and not right:
return True
if not left or not right:
return False
return (left.val == right.val and
is_mirror(left.left, right.right) and
is_mirror(left.right, right.left))
return is_mirror(root.left, root.right)
sym = TreeNode(1)
sym.left = TreeNode(2)
sym.right = TreeNode(2)
sym.left.left = TreeNode(3)
sym.right.right = TreeNode(3)
print(is_symmetric(sym)) # True
nosym = TreeNode(1)
nosym.left = TreeNode(2)
nosym.right = TreeNode(2)
nosym.left.right = TreeNode(3)
print(is_symmetric(nosym)) # FalseCombiner les notions de hauteur et de diamètre
Le schéma en postordre à un seul passage, dans lequel une fonction auxiliaire renvoie simultanément la hauteur et met à jour un résultat global, est réutilisable pour de nombreux problèmes : diamètre, somme de chemin maximale, vérification de l'équilibre, comptage des bons nœuds, et bien d'autres. Posez-vous toujours la question suivante : « De quelles informations le parent a-t-il besoin de la part de chaque enfant ? » C'est la valeur renvoyée. « Quel calcul est local à ce nœud ? » C'est ce qui met à jour la réponse globale. Cette décomposition est la compétence clé pour résoudre les problèmes difficiles sur les arbres.
# Reusable template for post-order dual-purpose DFS:
def tree_problem(root):
result = [float('-inf')] # or 0 depending on problem
def dfs(node):
if not node:
return 0 # base return (height, count, etc.)
left_val = dfs(node.left)
right_val = dfs(node.right)
# --- Update global result using both children ---
candidate = left_val + right_val # example: diameter
result[0] = max(result[0], candidate)
# --- Return info needed by PARENT ---
return 1 + max(left_val, right_val) # example: height
dfs(root)
return result[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(tree_problem(root)) # diameter = 2Vérification rapide
Testez votre compréhension des concepts de structures de données et d'algorithmes — préparation aux entretiens de programmation — abordés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris : le calcul de la hauteur à l'aide d'un DFS récursif en postordre, le calcul du diamètre en un seul passage O(n) à l'aide d'une fonction auxiliaire DFS à double rôle, et la vérification de l'équilibre avec un indicateur d'arrêt anticipé. Nous allons maintenant aborder les problèmes de somme de chemin et de plus bas ancêtre commun.
Questions Fréquemment Posées
La leçon « Diamètre, hauteur et arbres équilibrés » est-elle gratuite ?
Oui — le texte complet de « Diamètre, hauteur et arbres équilibrés » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours DSA Interview Prep, passe à CoddyKit PRO. Le cours DSA Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Diamètre, hauteur et arbres équilibrés » ?
Calculez le diamètre et la hauteur d’un arbre en un seul parcours DFS grâce à une fonction auxiliaire qui renvoie les deux valeurs, puis vérifiez si l’arbre est équilibré en hauteur. Tu pratiques DSA Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer DSA Interview Prep ?
Aucune expérience préalable n'est requise. DSA Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Diamètre, hauteur et arbres équilibrés » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon DSA Interview Prep ?
Oui. Chaque leçon DSA Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- Classe TreeNode et parcours BFS par niveaux
- DFS infixe, préfixe et postfixe
- Diamètre, hauteur et arbres équilibrés
- Somme des chemins et ancêtre commun le plus bas