Somme des chemins et ancêtre commun le plus bas
Résolvez la somme d’un chemin de la racine à une feuille, la somme de tous les chemins et la recherche de l’ancêtre commun le plus bas dans un arbre binaire général par descente récursive.
Somme des chemins et ancêtre commun le plus bas est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 4 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 Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Somme d'un chemin de la racine à la feuille
Le problème de somme de chemin consiste à déterminer si un chemin quelconque de la racine à une feuille donne une somme égale à une cible. Transmettez la cible restante lors de la récursion, en soustrayant la valeur de chaque nœud. À une feuille, vérifiez si la cible restante est égale à la valeur de la feuille. Cette méthode évite de gérer une liste de chemin explicite et utilise peu d'espace tout en restant claire. Cas limite : un arbre vide ne contient aucun chemin ; renvoyez donc False immédiatement.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def has_path_sum(root, target):
if not root:
return False
if not root.left and not root.right: # leaf
return root.val == target
remain = target - root.val
return (has_path_sum(root.left, remain) or
has_path_sum(root.right, remain))
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->2Tous les chemins de la racine à la feuille
Pour énumérer tous les chemins, conservez une liste représentant le chemin en cours. À chaque appel récursif, ajoutez la valeur du nœud courant avec append, explorez les enfants, puis utilisez pop au retour (retour arrière). À une feuille, enregistrez un instantané (list(path)) du chemin courant. Ce schéma — choisir, explorer, annuler le choix — est à la base du retour arrière sur les arbres.
def all_path_sums(root, target):
results = []
def dfs(node, path, remaining):
if not node:
return
path.append(node.val)
if not node.left and not node.right and remaining == node.val:
results.append(list(path)) # snapshot
else:
dfs(node.left, path, remaining - node.val)
dfs(node.right, path, remaining - node.val)
path.pop() # backtrack
dfs(root, [], target)
return results
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(8)
root.left.left = TreeNode(11)
root.left.left.right = TreeNode(2)
root.right.right = TreeNode(5)
print(all_path_sums(root, 22)) # [[5,4,11,2]]Somme de chemin III : tout chemin, tout nœud
La somme de chemin III (LeetCode n° 437) compte les chemins dont la somme est égale à une cible, le chemin pouvant commencer et se terminer n'importe où (et pas seulement de la racine à une feuille). La méthode par force brute est en O(n²) : lancez un DFS depuis chaque nœud. La méthode optimale en O(n) utilise une table de hachage des sommes préfixes : suivez la somme cumulée et comptez le nombre d'occurrences précédentes de current_sum - target, selon le même principe que pour les sommes de sous-tableaux.
def path_sum_iii(root, target):
prefix_counts = {0: 1}
def dfs(node, running_sum):
if not node:
return 0
running_sum += node.val
count = prefix_counts.get(running_sum - target, 0)
prefix_counts[running_sum] = prefix_counts.get(running_sum, 0) + 1
count += dfs(node.left, running_sum)
count += dfs(node.right, running_sum)
prefix_counts[running_sum] -= 1 # backtrack
return count
return dfs(root, 0)
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(-3)
root.left.left = TreeNode(3)
root.left.right = TreeNode(2)
root.right.right = TreeNode(11)
root.left.left.left = TreeNode(3)
root.left.left.right = TreeNode(-2)
root.left.right.right = TreeNode(1)
print(path_sum_iii(root, 8)) # 3Qu'est-ce que le plus bas ancêtre commun ?
Le plus bas ancêtre commun (LCA) de deux nœuds p et q dans un arbre binaire est le nœud le plus profond qui possède p et q parmi ses descendants (un nœud peut être son propre descendant). Le LCA intervient dans des problèmes tels que la « distance entre deux nœuds », le « chemin entre deux nœuds » et les requêtes d'intervalle sur les BST. Comprendre le LCA est essentiel pour les problèmes intermédiaires sur les arbres.
# 3
# / \
# 5 1
# / \ / \
# 6 2 0 8
# / \
# 7 4
# LCA(5, 1) = 3 (root)
# LCA(5, 4) = 5 (p itself is ancestor of q)
# LCA(6, 4) = 5
# LCA(7, 4) = 2
# Key insight: the LCA is the node where p and q
# first 'split' into different subtrees.
print('LCA: deepest node that is ancestor of both p and q')Algorithme récursif de LCA
La solution récursive élégante du LCA renvoie le premier nœud qui est soit p soit q, soit possède les deux dans ses sous-arbres. Si le nœud courant est p ou q, renvoyez-le. Sinon, explorez récursivement les sous-arbres gauche et droit. Si les deux côtés renvoient une valeur non nulle, le nœud courant est le LCA. Si un seul côté renvoie une valeur non nulle, faites remonter ce résultat. Cette solution s'exécute en O(n) dans le temps et utilise O(h) espace.
def lowest_common_ancestor(root, p, q):
# Base case: empty or found one of the targets
if not root or root == p or root == q:
return root
# Search both subtrees
left = lowest_common_ancestor(root.left, p, q)
right = lowest_common_ancestor(root.right, p, q)
# If both sides found something, this node is the LCA
if left and right:
return root
# Otherwise, return whichever side found something
return left if left else right
root = TreeNode(3)
root.left = TreeNode(5)
root.right = TreeNode(1)
root.left.left = TreeNode(6)
root.left.right = TreeNode(2)
p, q = root.left, root.right # 5 and 1
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 3LCA lorsqu'un nœud peut être son propre ancêtre
Un cas limite important se présente lorsque p est un ancêtre de q (ou inversement) : le LCA est p lui-même. L'algorithme récursif gère automatiquement ce cas : lorsqu'il atteint p, il renvoie immédiatement p sans explorer les sous-arbres de p. Le parent constate qu'un côté a renvoyé p et que l'autre a renvoyé une valeur nulle ; il fait donc remonter p comme LCA. Vérifiez toujours ce cas dans vos tests lorsque vous codez le LCA.
# Test case: p is ancestor of q
# Tree: 3 -> left=5 -> left=6
# LCA(5, 6) should be 5
root = TreeNode(3)
root.left = TreeNode(5)
root.left.left = TreeNode(6)
p = root.left # node 5
q = root.left.left # node 6
lca = lowest_common_ancestor(root, p, q)
print(lca.val) # 5 (p itself is the LCA)LCA avec des pointeurs de parent
Si chaque nœud possède un pointeur de parent, le LCA se réduit au problème de l'« intersection de deux listes chaînées ». Placez les ancêtres de p dans un ensemble, puis remontez depuis q jusqu'à trouver un nœud présent dans cet ensemble. Cette approche, en O(h) dans le temps et O(h) en espace, est courante lors des entretiens de conception de systèmes, lorsque vous contrôlez la structure des nœuds et pouvez stocker des références vers les parents.
class NodeWithParent:
def __init__(self, val, parent=None):
self.val = val
self.parent = parent
self.left = None
self.right = None
def lca_with_parent(p, q):
ancestors = set()
# Collect all ancestors of p
node = p
while node:
ancestors.add(node)
node = node.parent
# Walk up from q until we hit a known ancestor
node = q
while node:
if node in ancestors:
return node
node = node.parent
return None
print('With parent pointers: O(h) time and space')LCA dans un arbre binaire de recherche
Dans un BST, le LCA est plus simple à trouver, car la propriété d'ordre indique dans quel sous-arbre se trouve chaque nœud. Si p et q sont tous deux plus petits que le nœud courant, le LCA se trouve dans le sous-arbre gauche. S'ils sont tous deux plus grands, il se trouve dans le sous-arbre droit. Sinon, le nœud courant les sépare et constitue donc le LCA. Pour les BST équilibrés, cela ramène la complexité du problème à O(log n).
def lca_bst(root, p, q):
if not root:
return None
if p.val < root.val and q.val < root.val:
return lca_bst(root.left, p, q) # both in left
if p.val > root.val and q.val > root.val:
return lca_bst(root.right, p, q) # both in right
return root # split point = LCA
# Iterative BST LCA (no recursion overhead):
def lca_bst_iter(root, p, q):
while root:
if p.val < root.val and q.val < root.val:
root = root.left
elif p.val > root.val and q.val > root.val:
root = root.right
else:
return root
return None
print('BST LCA: O(log n) for balanced trees')Distance entre deux nœuds
La distance entre deux nœuds d'un arbre correspond au nombre d'arêtes du chemin qui les relie. Elle se calcule directement à partir du LCA : distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Commencez par trouver le LCA, puis calculez la profondeur de chaque nœud. Avec une fonction auxiliaire adaptée, cette méthode s'exécute en O(n) dans le temps et utilise O(h) espace.
def find_depth(root, target, depth=0):
if not root:
return -1
if root == target:
return depth
left = find_depth(root.left, target, depth + 1)
if left != -1:
return left
return find_depth(root.right, target, depth + 1)
def node_distance(root, p, q):
lca = lowest_common_ancestor(root, p, q)
# depth from LCA to p and q
dp = find_depth(lca, p)
dq = find_depth(lca, q)
return dp + dq
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(node_distance(root, root.left.left, root.left.right)) # 2Chemin de somme maximale de la racine à la feuille
Le chemin de somme maximale de la racine à la feuille suit la somme cumulée depuis la racine jusqu'au nœud courant. Aux feuilles, comparez cette somme à un maximum global. Il s'agit d'un DFS en préordre, où la somme du chemin courant est transmise comme paramètre. Contrairement à la somme de chemin maximale générique, cette version est limitée aux chemins allant de la racine à une feuille ; elle est donc plus simple, car il n'est pas nécessaire d'examiner des chemins arbitraires entre deux nœuds.
def max_root_to_leaf_sum(root):
if not root:
return float('-inf')
best = [float('-inf')]
def dfs(node, running):
running += node.val
if not node.left and not node.right: # leaf
best[0] = max(best[0], running)
return
if node.left:
dfs(node.left, running)
if node.right:
dfs(node.right, running)
dfs(root, 0)
return best[0]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(max_root_to_leaf_sum(root)) # 1+2+5 = 8Somme des nombres de la racine à la feuille
Somme des nombres de la racine à la feuille (LeetCode n° 129) traite chaque chemin de la racine à une feuille comme un nombre décimal (par exemple, le chemin 1→2→3 représente le nombre 123) et demande leur somme. Construisez le nombre en transmettant current_number * 10 + node.val lors de la récursion. À chaque feuille, ajoutez le nombre obtenu au total. C'est un exemple clair de DFS en préordre transmettant un état cumulé vers le bas.
def sum_numbers(root):
def dfs(node, num):
if not node:
return 0
num = num * 10 + node.val
if not node.left and not node.right: # leaf
return num
return dfs(node.left, num) + dfs(node.right, num)
return dfs(root, 0)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(sum_numbers(root)) # 12 + 13 = 25
root2 = TreeNode(4)
root2.left = TreeNode(9)
root2.right = TreeNode(0)
root2.left.left = TreeNode(5)
root2.left.right = TreeNode(1)
print(sum_numbers(root2)) # 495 + 491 + 40 = 1026Vé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 : les variantes de la somme de chemin (de la racine à la feuille, tous les chemins, somme de chemin III avec sommes préfixes), le plus bas ancêtre commun à l'aide d'une élégante séparation récursive, et le LCA dans un BST en O(log n) grâce à la propriété d'ordre. Nous allons maintenant commencer l'étude des arbres binaires de recherche avec les opérations d'insertion et de recherche.
Questions Fréquemment Posées
La leçon « Somme des chemins et ancêtre commun le plus bas » est-elle gratuite ?
Oui — le texte complet de « Somme des chemins et ancêtre commun le plus bas » 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 Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Somme des chemins et ancêtre commun le plus bas » ?
Résolvez la somme d’un chemin de la racine à une feuille, la somme de tous les chemins et la recherche de l’ancêtre commun le plus bas dans un arbre binaire général par descente récursive. Tu pratiques Coding 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 Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding 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 4 sur 4.
Combien de temps prend la leçon « Somme des chemins et ancêtre commun le plus bas » ?
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 Coding Interview Prep ?
Oui. Chaque leçon Coding 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