DFS in-order, pre-order e post-order
Implementi ricorsivamente e iterativamente tutti e tre i percorsi DFS con uno stack esplicito, spiegando quando è utile ciascun ordine
DFS in-order, pre-order e post-order è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Tre ordini di visita DFS
La DFS su un albero binario visita i nodi secondo uno dei tre ordini, in base a quando viene elaborata la radice rispetto ai figli. Preordine: radice → sinistro → destro. Inordine: sinistro → radice → destro. Postordine: sinistro → destro → radice. I nomi indicano dove viene collocata la radice nella sequenza. Comprendere tutti e tre è essenziale, perché problemi diversi richiedono ordini diversi.
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')Visita ricorsiva in preordine
Nel preordine, il nodo corrente viene elaborato prima dei suoi sottoalberi. Questo rispecchia la naturale lettura dall'alto verso il basso di un albero ed è usato per copiare alberi, serializzarli e valutare espressioni in notazione prefissa. L'implementazione ricorsiva è molto breve, ma costruisce uno stack di chiamate di profondità O(h), dove h è l'altezza dell'albero.
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]Visita ricorsiva in inordine
La visita inordine percorre il sottoalbero sinistro, poi la radice e infine il sottoalbero destro. Per un albero binario di ricerca, la visita inordine produce sempre una sequenza ordinata: questa proprietà viene sfruttata da problemi come la validazione di un BST, la ricerca del k-esimo elemento più piccolo e la conversione di un BST in un array ordinato. È la visita più importante da conoscere per i problemi sui 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!Visita ricorsiva in postordine
La visita in postordine elabora entrambi i figli prima del nodo corrente. Quest'ordine dal basso verso l'alto è naturale quando il calcolo del padre dipende dai risultati dei figli, per esempio nel calcolo delle dimensioni dei sottoalberi, nell'eliminazione di un albero o nella valutazione di un albero delle espressioni. La maggior parte dei problemi sugli alberi in cui si trasferiscono informazioni verso l'alto utilizza una logica postordine implicita.
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]Visita iterativa in preordine con uno stack
Per evitare i limiti della profondità di ricorsione, implementi DFS in modo iterativo usando uno stack esplicito. Nel preordine: inserisca la radice nello stack, poi a ogni iterazione estragga un nodo, lo registri e inserisca prima il figlio destro e poi quello sinistro (prima il destro, così il sinistro viene elaborato per primo). Questo riproduce il comportamento LIFO dello stack delle chiamate ed è l'approccio preferito per gli alberi profondi, nei quali il limite predefinito di ricorsione di Python, pari a 1000, causerebbe un errore.
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]Visita iterativa in inordine con uno stack
La visita iterativa inordine è leggermente più complessa. Utilizzi uno stack e un puntatore curr: proceda verso sinistra il più possibile, inserendo ogni nodo nello stack. Quando non può più procedere verso sinistra, estragga un nodo, lo registri e poi si sposti a destra. Questo schema — inserire a sinistra fino a null, estrarre ed elaborare, quindi procedere a destra — è una tecnica iterativa fondamentale che ricorre nei problemi sugli iteratori 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]Visita iterativa in postordine con due stack
La visita iterativa in postordine presenta un trucco elegante: esegua una visita in preordine modificata (radice → destra → sinistra) e raccolga i risultati in ordine inverso. Inserisca la radice, estragga un nodo e lo aggiunga all'inizio del risultato, quindi inserisca prima il figlio sinistro e poi quello destro. L'inversione trasforma radice-destra-sinistra in sinistra-destra-radice, che corrisponde esattamente al postordine. In alternativa, utilizzi un puntatore prev per tenere traccia dell'ultimo nodo visitato usando un solo stack.
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]Quando scegliere quale visita
Scegliere la visita corretta è un indicatore importante in un colloquio. Utilizzi il preordine quando deve elaborare un padre prima dei suoi figli, per esempio per serializzare un albero o copiarne la struttura. Utilizzi l'inordine per i BST, sfruttando l'ordinamento crescente. Utilizzi il postordine per calcolare valori che dipendono da entrambi i figli, come altezza, diametro e somma del sottoalbero. BFS è preferibile per i problemi di percorso minimo e raggruppamento per livelli.
# 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)) # 6Visita di Morris in inordine con spazio O(1)
La visita di Morris raggiunge uno spazio O(1) in inordine modificando temporaneamente l'albero. Per ogni nodo con un sottoalbero sinistro, individui il predecessore inordine, cioè il nodo più a destra del sottoalbero sinistro, e colleghi il suo puntatore destro al nodo corrente. Dopo averlo visitato, ripristini il collegamento. Questa tecnica avanzata viene richiesta nei colloqui più selettivi quando l'intervistatore chiede: «Può farlo con spazio aggiuntivo 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]Ricostruzione dell'albero dalle visite
Forniti gli array di preordine e inordine, è possibile ricostruire l'albero originale. Il primo elemento del preordine è sempre la radice. Individui tale radice nell'array inordine: tutto ciò che si trova alla sua sinistra appartiene al sottoalbero sinistro, mentre tutto ciò che si trova alla sua destra appartiene al sottoalbero destro. Applichi ricorsivamente la stessa procedura ai sottoarray. La complessità temporale è O(n) utilizzando una mappa hash per cercare l'indice.
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 20Riepilogo di tempo e spazio delle visite
Tutte e tre le visite DFS hanno una complessità temporale O(n), perché ogni nodo viene visitato esattamente una volta. La complessità spaziale è O(h), dove h è l'altezza dell'albero: O(log n) per gli alberi bilanciati e O(n) per quelli sbilanciati, a causa dello stack delle chiamate o dello stack esplicito. Le implementazioni iterative evitano il limite di ricorsione di Python, ma utilizzano lo stesso spazio asintotico. La visita di Morris raggiunge in modo unico uno spazio O(1) riutilizzando i puntatori destri dell'albero.
# 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')Verifica rapida
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: i tre ordini di visita DFS (preordine, inordine e postordine) e quando scegliere ciascuno, le implementazioni ricorsive e iterative usando uno stack esplicito e la tecnica di Morris con spazio O(1). Ora esplorerà il calcolo del diametro, dell'altezza e dell'equilibrio degli alberi binari.
Domande Frequenti
La lezione «DFS in-order, pre-order e post-order» è gratuita?
Sì — il testo completo di «DFS in-order, pre-order e post-order» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «DFS in-order, pre-order e post-order»?
Implementi ricorsivamente e iterativamente tutti e tre i percorsi DFS con uno stack esplicito, spiegando quando è utile ciascun ordine Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «DFS in-order, pre-order e post-order»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Classe TreeNode e BFS per livelli
- DFS in-order, pre-order e post-order
- Diametro, altezza e alberi bilanciati
- Somma dei percorsi e antenato comune più vicino