Classe TreeNode e BFS per livelli
Costruisca alberi binari a partire da array, implementi BFS con una deque per stamparli livello per livello e risolva maximum-depth usando BFS
Classe TreeNode e BFS per livelli è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 1 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 Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Le basi della classe TreeNode
Un albero binario è una struttura dati gerarchica in cui ogni nodo ha al massimo due figli, chiamati left e right. In Python, si modella un nodo con una semplice classe: class TreeNode: def __init__(self, val=0, left=None, right=None). Ogni problema sugli alberi nei colloqui parte da questa definizione: la si incontrerà nel codice di base di quasi tutti i problemi sugli alberi di LeetCode.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build a small tree manually:
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(root.val, root.left.val, root.right.val)Costruire alberi a partire da array
Nei problemi dei colloqui, spesso viene fornito un albero rappresentato come un array in ordine di livello, in cui None indica i nodi mancanti. Dato l'indice i, il figlio sinistro si trova in posizione 2i+1 e quello destro in posizione 2i+2. Scrivere un helper per deserializzare questo array in oggetti TreeNode collegati è un'utilità preziosa che consente di risparmiare tempo durante le esercitazioni.
from collections import deque
def build_tree(arr):
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
q = deque([root])
i = 1
while q and i < len(arr):
node = q.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
q.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
q.append(node.right)
i += 1
return root
root = build_tree([1, 2, 3, 4, 5, None, 6])
print(root.val, root.left.val, root.right.val)Che cos'è la BFS e perché una coda?
La ricerca in ampiezza (BFS) visita tutti i nodi alla profondità d prima di visitare qualsiasi nodo alla profondità d+1. Questo attraversamento livello per livello è esattamente ciò che fornisce una coda (FIFO): si inserisce la radice nella coda, poi si elaborano i nodi uno alla volta, inserendo man mano i figli di ciascun nodo. collections.deque di Python fornisce appendleft e popleft in O(1), perciò è la scelta corretta rispetto a una semplice lista.
from collections import deque
def bfs_print(root):
if not root:
return
q = deque([root])
while q:
node = q.popleft()
print(node.val, end=' ')
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
bfs_print(root) # 1 2 3 4BFS in ordine di livello: raggruppare per livello
La variante standard della BFS raggruppa i nodi per livello registrando la dimensione della coda all'inizio di ogni iterazione. Si elaborano esattamente quel numero di nodi, se ne raccolgono i valori e poi si passa al livello successivo. Si ottiene così una lista di liste, un formato di output molto comune nei colloqui per problemi come attraversamento di un albero binario in ordine di livello, attraversamento a zigzag e vista dal lato destro.
from collections import deque
def level_order(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
level = []
for _ in range(level_size):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order(root)) # [[1], [2, 3], [4]]Profondità massima tramite BFS
La profondità massima di un albero binario è uguale al numero di livelli nel suo attraversamento BFS. È sufficiente contare quante volte si completa il ciclo di elaborazione di un livello. Si ottiene una soluzione con complessità temporale O(n) e spaziale O(w), dove w è la larghezza massima dell'albero. Per un albero bilanciato, w è O(n/2), quindi lo spazio nel caso peggiore è O(n).
from collections import deque
def max_depth_bfs(root):
if not root:
return 0
depth = 0
q = deque([root])
while q:
depth += 1
for _ in range(len(q)):
node = q.popleft()
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return depth
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(max_depth_bfs(root)) # 3Vista dal lato destro di un albero binario
La vista dal lato destro restituisce l'ultimo nodo visibile osservando l'albero da destra, cioè l'ultimo elemento di ogni livello nell'attraversamento BFS. È un'applicazione diretta della BFS in ordine di livello: si raccoglie l'ultimo nodo durante l'elaborazione di ciascun livello. La complessità temporale è O(n), mentre quella spaziale è O(w) per la coda.
from collections import deque
def right_side_view(root):
if not root:
return []
result = []
q = deque([root])
while q:
level_size = len(q)
for i in range(level_size):
node = q.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.right = TreeNode(5)
print(right_side_view(root)) # [1, 3, 5]Visita a zigzag per livelli
Nella visita a zigzag, i livelli dispari vengono raccolti da sinistra a destra e quelli pari da destra a sinistra. L'implementazione più pulita mantiene invariata la coda BFS e si limita a invertire alternativamente le liste dei livelli prima di aggiungerle al risultato. Tracci la direzione con un flag booleano che cambia a ogni livello. In questo modo si evita la complessità di una deque a doppia estremità nel ciclo interno.
from collections import deque
def zigzag_level_order(root):
if not root:
return []
result = []
q = deque([root])
left_to_right = True
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(level if left_to_right else level[::-1])
left_to_right = not left_to_right
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(zigzag_level_order(root))Analisi della complessità spaziale di BFS
BFS utilizza uno spazio O(w), dove w è la larghezza massima dell'albero. In un albero binario perfetto con n nodi, l'ultimo livello contiene (n+1)/2 nodi, quindi BFS può arrivare a contenere contemporaneamente fino a n/2 nodi nella coda. Per gli alberi bilanciati e molto larghi, questo rende BFS peggiore di DFS in termini di spazio (O(h)); è invece migliore per gli alberi profondi e sbilanciati, in cui la profondità dello stack delle chiamate di DFS è pari a n.
# Space comparison: BFS vs DFS on a complete binary tree
# n=15 nodes, height=4
# BFS max queue size = 8 (last level)
# DFS max call stack = 4 (height)
# For a skewed tree (like a linked list):
# n=1000 nodes
# BFS max queue size = 1 (always 1 node per level)
# DFS max call stack = 1000 (recursion depth -> stack overflow!)
from collections import deque
def skewed_tree(n):
root = TreeNode(1)
cur = root
for i in range(2, n+1):
cur.right = TreeNode(i)
cur = cur.right
return root
root = skewed_tree(10)
print('BFS on skewed tree is safe')Media dei livelli di un albero binario
Calcolare la media dei valori a ogni livello è un'altra applicazione diretta di BFS. Sommi tutti i valori di un livello, divida per il numero di nodi e aggiunga il risultato alla lista dei risultati. Questo problema verifica che sappia eseguire calcoli aritmetici all'interno del ciclo del livello. Utilizzi sempre la divisione in virgola mobile in Python 3 (l'operatore /) e gestisca il caso limite dell'albero vuoto all'inizio.
from collections import deque
def average_of_levels(root):
if not root:
return []
result = []
q = deque([root])
while q:
size = len(q)
total = 0
for _ in range(size):
node = q.popleft()
total += node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
result.append(total / size)
return result
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)
print(average_of_levels(root)) # [3.0, 14.5, 11.0]Profondità minima tramite BFS
La profondità minima è la distanza dalla radice al nodo foglia più vicino, cioè un nodo senza figli. BFS la trova in modo ottimale: il primo nodo foglia incontrato durante la visita per livelli si trova sicuramente alla profondità minima. Restituisca la profondità corrente non appena raggiunge una foglia. Nel caso peggiore la complessità è O(n), ma per gli alberi bilanciati spesso l'algoritmo termina molto prima.
from collections import deque
def min_depth(root):
if not root:
return 0
q = deque([(root, 1)])
while q:
node, depth = q.popleft()
# A leaf has no children
if not node.left and not node.right:
return depth
if node.left:
q.append((node.left, depth + 1))
if node.right:
q.append((node.right, depth + 1))
return 0
root = TreeNode(2)
root.left = TreeNode(3)
root.left.left = TreeNode(4)
root.right = TreeNode(5) # leaf at depth 2
print(min_depth(root)) # 2Collegamento dei nodi fratelli allo stesso livello
Il problema dei puntatori next-right chiede di collegare ogni nodo al suo vicino destro allo stesso livello. Con BFS è semplice: all'interno del ciclo di ciascun livello, imposti node.next = q[0] per tutti i nodi tranne l'ultimo. È un esempio classico in cui BFS rende la soluzione immediata, mentre DFS richiede un tracciamento accurato dei puntatori tra i sottoalberi.
from collections import deque
class Node:
def __init__(self, val=0, left=None, right=None, next=None):
self.val = val
self.left = left
self.right = right
self.next = next
def connect(root):
if not root:
return root
q = deque([root])
while q:
size = len(q)
for i in range(size):
node = q.popleft()
if i < size - 1:
node.next = q[0]
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
return root
print('BFS connect: O(n) time, O(w) space')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: la definizione della classe TreeNode e come costruire alberi da array, la visita BFS per livelli usando una deque con il trucco delle dimensioni del livello per raggruppare i nodi e le applicazioni, tra cui profondità massima, profondità minima, vista dal lato destro, visita a zigzag e media dei livelli. Ora esplorerà gli ordini delle visite DFS ricorsive.
Domande Frequenti
La lezione «Classe TreeNode e BFS per livelli» è gratuita?
Sì — il testo completo di «Classe TreeNode e BFS per livelli» è 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 Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Classe TreeNode e BFS per livelli»?
Costruisca alberi binari a partire da array, implementi BFS con una deque per stamparli livello per livello e risolva maximum-depth usando BFS Eserciti Coding 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 Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding 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 1 di 4.
Quanto tempo richiede la lezione «Classe TreeNode e BFS per livelli»?
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 Coding Interview Prep?
Sì. Ogni lezione Coding 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