Diametro, altezza e alberi bilanciati
Calcoli diametro e altezza dell'albero in un'unica scansione DFS usando un helper che restituisce entrambi i valori, poi verifichi se l'albero è bilanciato in altezza
Diametro, altezza e alberi bilanciati è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 3 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.
Altezza di un albero binario
L'altezza (o profondità massima) di un albero binario è la lunghezza del percorso più lungo dalla radice a una foglia qualsiasi. Si calcola ricorsivamente: l'altezza di un nodo è 1 + max(height(left), height(right)), con un caso base pari a 0 per i nodi null. Questo calcolo postordine è fondamentale: l'altezza è la base per il diametro, la verifica dell'equilibrio e le rotazioni degli alberi 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)) # 4Diametro: il percorso più lungo
Il diametro di un albero binario è la lunghezza del percorso più lungo tra due nodi qualsiasi; il percorso può passare o meno per la radice. La lunghezza del percorso viene misurata in archi. Per ogni nodo, il diametro che passa da quel nodo equivale a height(left) + height(right). Il diametro complessivo è il massimo di questo valore tra tutti i nodi dell'albero.
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'unica passata DFS per il diametro
L'approccio ingenuo chiama height() per ogni nodo, con complessità O(n²) per un albero bilanciato. La soluzione ottimale calcola l'altezza e aggiorna il diametro in un'unica passata DFS. L'intuizione fondamentale è che la funzione ricorsiva dfs() svolge due funzioni contemporaneamente: restituisce l'altezza al nodo padre e aggiorna un diametro massimo globale come effetto collaterale. Questo schema postordine a doppio scopo ricorre in molti problemi sugli alberi.
# 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)')Verifica dell'equilibrio di un albero binario
Un albero binario è bilanciato in altezza se le altezze dei sottoalberi sinistro e destro di ogni nodo differiscono al massimo di uno. L'approccio a forza bruta chiama height() per ogni nodo, con complessità O(n²). L'approccio ottimale utilizza lo stesso trucco della singola passata: restituisce -1 come sentinella per indicare «non bilanciato» e propaga tale valore verso l'alto, interrompendo il calcolo non appena trova un nodo non bilanciato.
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)) # FalseIl modello del valore sentinella restituito
Restituire un valore sentinella (-1 per un albero non bilanciato o una tupla speciale) è un modello comune quando una funzione di supporto DFS deve segnalare due tipi di informazioni: il risultato calcolato e l'eventuale violazione di un vincolo. Invece di sollevare eccezioni o utilizzare flag globali, codifichi l'errore nel tipo restituito. Questo approccio è pulito, evita lo stato globale e si compone naturalmente con altre funzioni ricorsive di supporto.
# 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 2Diametro in termini di nodi e archi
Faccia attenzione alla formulazione del problema: LeetCode #543 misura il diametro in archi, mentre alcuni problemi lo misurano in nodi. Se serve il conteggio dei nodi, il diametro che passa da un nodo è height(left) + height(right) + 1 (si aggiunge 1 per il nodo stesso). Se serve il conteggio degli archi, si omette +1. Chiarisca sempre questo aspetto con l'intervistatore prima di scrivere il codice.
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-3Somma del percorso: qualsiasi percorso dalla radice a una foglia
Il problema della somma del percorso chiede: esiste un percorso dalla radice a una foglia la cui somma è uguale a un valore obiettivo? Utilizzi DFS e sottragga il valore del nodo corrente dall'obiettivo mentre scende nell'albero. Quando raggiunge una foglia, verifichi se l'obiettivo rimanente coincide con il valore della foglia. Si tratta di una DFS in preordine in cui si passa la somma rimanente come parametro: un esempio classico di ricorsione dall'alto verso il basso.
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=22Somma massima di un percorso (variante difficile)
La somma massima di un percorso (LeetCode #124) è molto più complessa: il percorso può iniziare e terminare in un nodo qualsiasi, non solo in un percorso dalla radice a una foglia, e i valori possono essere negativi. Per ogni nodo, consideri quattro opzioni: solo il nodo, nodo + ramo sinistro, nodo + ramo destro oppure nodo + entrambi i rami. Solo le prime tre possono essere estese verso il nodo padre; la quarta è un candidato terminale per il massimo globale.
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+7Alberi AVL e autobilanciamento
Un albero AVL è un BST che mantiene la proprietà di equilibrio in altezza eseguendo rotazioni dopo le operazioni di inserimento ed eliminazione. Ogni nodo memorizza un fattore di bilanciamento (height(right) - height(left)), che deve rimanere in {-1, 0, 1}. Quando si verifica una violazione, una rotazione singola o doppia ripristina l'equilibrio in O(1), mantenendo l'altezza complessiva in O(log n) e garantendo che tutte le operazioni siano 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')Verifica della simmetria di un albero
Un albero binario è simmetrico se è l'immagine speculare di sé stesso. Verifichi ricorsivamente: l'albero è simmetrico se, per ogni coppia di nodi corrispondenti ai due lati dell'asse, i valori sono uguali e i sottoalberi sono speculari. Definisca una funzione di supporto is_mirror(left, right) che controlli: entrambi null (corretto), uno null (non corretto), valori uguali e sottoalberi interno ed esterno speculari.
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)) # FalseCombinare le informazioni su altezza e diametro
Lo schema post-order a passaggio singolo, in cui una funzione di supporto restituisce contemporaneamente l’altezza e aggiorna un risultato globale, è riutilizzabile in molti problemi: diametro, somma massima dei percorsi, verifica del bilanciamento, conteggio dei nodi validi e altro ancora. Si chieda sempre: «quali informazioni servono al genitore da ciascun figlio?». Questo è il valore restituito. «Quale calcolo è locale a questo nodo?». Questo aggiorna il risultato globale. Questa scomposizione è la competenza chiave per affrontare problemi complessi sugli alberi.
# 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 = 2Verifica rapida
Verifichi la comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep affrontati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: il calcolo dell’altezza usando una DFS ricorsiva post-order, il calcolo del diametro in un unico passaggio O(n) con una funzione di supporto DFS a doppio scopo e la verifica del bilanciamento con un sentinel di uscita anticipata. Ora affronteremo i problemi sulla somma dei percorsi e l’antenato comune più basso.
Domande Frequenti
La lezione «Diametro, altezza e alberi bilanciati» è gratuita?
Sì — il testo completo di «Diametro, altezza e alberi bilanciati» è 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 «Diametro, altezza e alberi bilanciati»?
Calcoli diametro e altezza dell'albero in un'unica scansione DFS usando un helper che restituisce entrambi i valori, poi verifichi se l'albero è bilanciato in altezza 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 3 di 4.
Quanto tempo richiede la lezione «Diametro, altezza e alberi bilanciati»?
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