DFS infixe, préfixe et postfixe
Implémentez récursivement et itérativement les trois parcours DFS avec une pile explicite, en expliquant dans quels cas chacun est utile.
DFS infixe, préfixe et postfixe est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 2 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.
Les trois ordres de parcours de DFS
Dans un arbre binaire, DFS visite les nœuds selon l’un des trois ordres possibles, en fonction du moment où la racine est traitée par rapport à ses enfants. Préordre : racine → gauche → droite. Inordre : gauche → racine → droite. Postordre : gauche → droite → racine. Les noms indiquent la position de la racine dans la séquence. Il est essentiel de comprendre les trois ordres, car différents problèmes exigent des parcours différents.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre: 1 2 4 5 3
# in: 4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')Parcours récursif en préordre
En préordre, le nœud courant est traité avant ses sous-arbres. Cela correspond à la lecture naturelle, de haut en bas, d’un arbre et sert à copier des arbres, à les sérialiser et à évaluer des expressions préfixées. L’implémentation récursive est très courte, mais elle construit une pile d’appels de profondeur O(h), où h représente la hauteur de l’arbre.
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
if result is None:
result = []
if not root:
return result
result.append(root.val) # PROCESS ROOT FIRST
preorder_v2(root.left, result)
preorder_v2(root.right, result)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root)) # [1, 2, 4, 5, 3]Parcours récursif en inordre
Le parcours en inordre visite le sous-arbre gauche, puis la racine, puis le sous-arbre droit. Pour un arbre binaire de recherche, le parcours en inordre produit toujours une séquence triée — cette propriété est utilisée dans des problèmes tels que la validation d’un BST, la recherche du k-ième plus petit élément et la conversion d’un BST en tableau trié. C’est le parcours le plus important à connaître pour les problèmes portant sur les BST.
def inorder(root, result=None):
if result is None:
result = []
if not root:
return result
inorder(root.left, result) # left subtree first
result.append(root.val) # PROCESS ROOT MIDDLE
inorder(root.right, result) # right subtree last
return result
# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
return root
bst = make_bst()
print(inorder(bst)) # [1, 2, 3, 4, 6] - sorted!Parcours récursif en postordre
Le parcours en postordre traite les deux enfants avant le nœud courant. Cet ordre ascendant est naturel lorsque le calcul du parent dépend des résultats de ses enfants — par exemple pour calculer la taille des sous-arbres, supprimer un arbre ou évaluer un arbre d’expressions. La plupart des problèmes sur les arbres qui transmettent des informations vers le haut utilisent une logique implicite de postordre.
def postorder(root, result=None):
if result is None:
result = []
if not root:
return result
postorder(root.left, result) # left subtree
postorder(root.right, result) # right subtree
result.append(root.val) # PROCESS ROOT LAST
return result
# Use case: delete a tree (children before parent)
def delete_tree(root):
if not root:
return
delete_tree(root.left)
delete_tree(root.right)
print(f'Deleting node {root.val}') # safe: children gone
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root)) # [4, 2, 3, 1]Préordre itératif avec une pile
Pour éviter les limites de profondeur de la récursion, implémentez DFS de manière itérative à l’aide d’une pile explicite. En préordre, empilez la racine, puis, à chaque itération, dépilez un nœud, enregistrez-le et empilez son enfant droit, puis son enfant gauche (le droit en premier afin que le gauche soit traité en premier). Cela reproduit le comportement LIFO de la pile d’appels et constitue l’approche de référence pour les arbres profonds, où la limite de récursion par défaut de Python, fixée à 1000, provoquerait un échec.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process now
if node.right: # push right FIRST
stack.append(node.right)
if node.left: # push left second (popped first)
stack.append(node.left)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Inordre itératif avec une pile
L’inordre itératif est légèrement plus délicat. Utilisez une pile et un pointeur curr : allez le plus loin possible vers la gauche en empilant chaque nœud. Lorsque vous ne pouvez plus aller vers la gauche, dépilez un nœud, enregistrez-le, puis allez vers la droite. Ce schéma — empiler vers la gauche jusqu’à null, dépiler et traiter, puis aller vers la droite — est une technique itérative fondamentale, que l’on retrouve dans les problèmes d’itérateur de BST.
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
# Go as far left as possible
while curr:
stack.append(curr)
curr = curr.left
# Pop and process
curr = stack.pop()
result.append(curr.val)
# Move to right subtree
curr = curr.right
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root)) # [4, 2, 5, 1, 3]Postordre itératif avec deux piles
Le postordre itératif repose sur une astuce élégante : effectuez un préordre modifié (racine → droite → gauche), puis collectez les résultats dans l’ordre inverse. Empilez la racine, dépilez un nœud et ajoutez-le au début du résultat, puis empilez l’enfant gauche et l’enfant droit. L’inversion transforme racine-droite-gauche en gauche-droite-racine, ce qui correspond exactement au postordre. Vous pouvez aussi utiliser un pointeur prev pour suivre le dernier nœud visité avec une seule pile.
from collections import deque
def postorder_iterative(root):
if not root:
return []
result = deque()
stack = [root]
while stack:
node = stack.pop()
result.appendleft(node.val) # prepend = reverse pre-order
if node.left:
stack.append(node.left) # push left first
if node.right:
stack.append(node.right) # push right second
return list(result)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root)) # [4, 5, 2, 3, 1]Quand choisir chaque parcours
Choisir le bon parcours est un indicateur important en entretien. Utilisez le préordre lorsque vous devez traiter un parent avant ses enfants (sérialiser un arbre, copier une structure). Utilisez l’inordre pour les BST afin de profiter de l’ordre trié. Utilisez le postordre lorsque vous calculez des valeurs qui dépendent des deux enfants (hauteur, diamètre, somme d’un sous-arbre). BFS est préférable pour les problèmes de plus court chemin et de regroupement par niveaux.
# Pattern summary:
# Pre-order -> top-down: parent info flows DOWN to children
# In-order -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS -> shortest path, level grouping, level averages
# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
if not root:
return 0
left = subtree_sum(root.left)
right = subtree_sum(root.right)
return root.val + left + right # uses children FIRST
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root)) # 6Parcours de Morris : espace O(1) en inordre
Le parcours de Morris réalise un parcours en inordre avec un espace O(1) en modifiant temporairement l’arbre. Pour chaque nœud possédant un sous-arbre gauche, trouvez le prédécesseur en inordre (le nœud le plus à droite du sous-arbre gauche) et reliez son pointeur droit au nœud courant. Après la visite, rétablissez le lien. Cette technique avancée est demandée dans les entretiens les plus sélectifs lorsque l’intervieweur demande : « pouvez-vous le faire avec un espace supplémentaire O(1) ? »
def morris_inorder(root):
result = []
curr = root
while curr:
if not curr.left:
result.append(curr.val)
curr = curr.right
else:
# Find in-order predecessor
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
# Make thread and move left
pred.right = curr
curr = curr.left
else:
# Remove thread, visit, move right
pred.right = None
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root)) # [1, 2, 3, 4, 6]Reconstruire un arbre à partir de parcours
À partir de tableaux en préordre et en inordre, vous pouvez reconstruire l’arbre d’origine. Le premier élément du préordre est toujours la racine. Trouvez cette racine dans le tableau en inordre : tout ce qui se trouve à sa gauche appartient au sous-arbre gauche, et tout ce qui se trouve à sa droite au sous-arbre droit. Appliquez récursivement cette méthode aux sous-tableaux. La complexité temporelle est O(n) grâce à une recherche d’index dans une table de hachage.
def build_from_preorder_inorder(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
# left subtree: inorder[0:mid], preorder[1:mid+1]
root.left = build_from_preorder_inorder(
preorder[1:mid+1], inorder[:mid])
# right subtree: inorder[mid+1:], preorder[mid+1:]
root.right = build_from_preorder_inorder(
preorder[mid+1:], inorder[mid+1:])
return root
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val) # 3 9 20Résumé des complexités temporelle et spatiale des parcours
Les trois parcours de DFS ont une complexité temporelle O(n), car chaque nœud est visité exactement une fois. La complexité spatiale est O(h), où h représente la hauteur de l’arbre : O(log n) pour les arbres équilibrés et O(n) pour les arbres dégénérés, en raison de la pile d’appels ou de la pile explicite. Les implémentations itératives évitent la limite de récursion de Python, mais utilisent le même espace asymptotique. Le parcours de Morris est le seul à atteindre un espace O(1), en réutilisant les pointeurs droits de l’arbre.
# Complexity table:
# Traversal | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order | O(n) | O(h) | O(h)
# In-order | O(n) | O(h) | O(h)
# Post-order | O(n) | O(h) | O(h)
# Morris | O(n) | O(1) | O(1)
# BFS | O(n) | O(w) | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')Vérification rapide
Testez votre compréhension des concepts de structures de données et d’algorithmes — préparation aux entretiens de programmation présentés dans cette leçon.
Récapitulatif de la leçon
Dans cette leçon, vous avez appris les trois ordres de parcours de DFS (préordre, inordre et postordre) et quand choisir chacun, les implémentations récursives et itératives à l’aide d’une pile explicite, ainsi que la technique de Morris avec un espace O(1). Nous allons maintenant étudier le calcul du diamètre, de la hauteur et de l’équilibre des arbres binaires.
Questions Fréquemment Posées
La leçon « DFS infixe, préfixe et postfixe » est-elle gratuite ?
Oui — le texte complet de « DFS infixe, préfixe et postfixe » 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 « DFS infixe, préfixe et postfixe » ?
Implémentez récursivement et itérativement les trois parcours DFS avec une pile explicite, en expliquant dans quels cas chacun est utile. 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 2 sur 4.
Combien de temps prend la leçon « DFS infixe, préfixe et postfixe » ?
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