Somma dei percorsi e antenato comune più vicino
Risolva root-to-leaf path sum, all-paths-sum e lowest-common-ancestor per un albero binario generico usando la discesa ricorsiva
Somma dei percorsi e antenato comune più vicino è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 4 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.
Somma dei percorsi dalla radice a una foglia
Il problema della somma del percorso chiede se esista un percorso dalla radice a una foglia la cui somma sia uguale a un valore obiettivo. Si passi il valore obiettivo rimanente nella ricorsione, sottraendo il valore di ciascun nodo. Quando si raggiunge una foglia, si verifichi se il valore rimanente è uguale al valore della foglia. In questo modo non è necessario mantenere un elenco esplicito del percorso e si ottiene una soluzione efficiente in termini di spazio e semplice da leggere. Caso limite: un albero vuoto non contiene percorsi, quindi si restituisca subito False.
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->2Tutti i percorsi dalla radice a una foglia
Per enumerare tutti i percorsi, si mantenga un elenco del percorso corrente. A ogni chiamata ricorsiva, si aggiunga il valore del nodo corrente, si esegua la ricorsione sui figli e poi si esegua pop al ritorno, effettuando il backtracking. Quando si raggiunge una foglia, si registri un’istantanea (list(path)) del percorso corrente. Questo schema — scegliere, ricorrere, annullare la scelta — è alla base del backtracking sugli alberi.
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]]Path Sum III: qualsiasi percorso, qualsiasi nodo
Path Sum III (LeetCode #437) conta i percorsi la cui somma è uguale a un valore obiettivo, consentendo al percorso di iniziare e terminare in punti qualsiasi, non necessariamente dalla radice a una foglia. L’approccio esaustivo ha complessità O(n²): si esegue una DFS a partire da ogni nodo. L’approccio ottimale O(n) usa una mappa hash delle somme prefisse: si tiene traccia della somma progressiva e si conta quante volte current_sum - target è comparsa in precedenza, in modo analogo all’approccio per la somma dei sottoarray.
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)) # 3Che cos’è l’antenato comune più basso?
L’antenato comune più basso (LCA) di due nodi p e q in un albero binario è il nodo più profondo che ha sia p sia q tra i propri discendenti; un nodo può essere discendente di sé stesso. L’LCA compare in problemi come «distanza tra due nodi», «percorso tra due nodi» e query sugli intervalli di un BST. Comprendere l’LCA è essenziale per affrontare problemi di livello intermedio sugli alberi.
# 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')Algoritmo ricorsivo per l’LCA
L’elegante soluzione ricorsiva per l’LCA restituisce il primo nodo che è p o q oppure che ha entrambi nei propri sottoalberi. Se il nodo corrente è p o q, lo si restituisce. Altrimenti, si esegue la ricorsione a sinistra e a destra. Se entrambi i lati restituiscono un valore non nullo, il nodo corrente è l’LCA. Se solo un lato restituisce un valore non nullo, si propaga quel risultato verso l’alto. La complessità è O(n) in termini di tempo e O(h) in termini di spazio.
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) # 3L’LCA quando un nodo può essere il proprio antenato
Un caso limite fondamentale: se p è un antenato di q, o viceversa, l’LCA è p stesso. L’algoritmo ricorsivo gestisce automaticamente questo caso: quando raggiunge p, restituisce subito p senza esaminare i sottoalberi di p. Il genitore vedrà che un lato ha restituito p e l’altro ha restituito null, quindi propagherà p verso l’alto come LCA. Quando si implementa l’LCA, si verifichi sempre questo caso nei test.
# 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)L’LCA con puntatori al genitore
Se ogni nodo dispone di un puntatore al genitore, l’LCA si riduce al problema dell’«intersezione di due liste collegate». Si raccolgano gli antenati di p in un insieme, poi si risalga da q finché non si trova un nodo presente in quell’insieme. Questo approccio, con complessità O(h) in termini di tempo e O(h) in termini di spazio, è comune nei colloqui di system design, quando si controlla la struttura dei nodi e si possono memorizzare i riferimenti ai genitori.
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')L’LCA in un albero binario di ricerca
In un BST, l’LCA è più semplice da trovare perché la proprietà di ordinamento indica quale sottoalbero contiene ciascun nodo. Se p e q sono entrambi minori del nodo corrente, l’LCA si trova nel sottoalbero sinistro. Se sono entrambi maggiori, si trova nel sottoalbero destro. In caso contrario, il nodo corrente li separa, quindi è l’LCA. Per i BST bilanciati, il problema si riduce a 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')Distanza tra due nodi
La distanza tra due nodi in un albero è uguale al numero di archi del percorso che li collega. Si calcola direttamente a partire dall’LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Si trovi prima l’LCA, poi si calcoli la profondità di ciascun nodo. Con una funzione di supporto adeguata, la complessità è O(n) in termini di tempo e O(h) in termini di spazio.
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)) # 2Somma massima del percorso dalla radice a una foglia
La somma massima del percorso dalla radice a una foglia tiene traccia della somma progressiva dalla radice al nodo corrente. Quando si raggiunge una foglia, la si confronta con il massimo globale. Si tratta di una DFS pre-order in cui la somma del percorso corrente viene passata come parametro. A differenza della somma massima generica di un percorso, questa variante è limitata ai percorsi dalla radice a una foglia, quindi è più semplice: non è necessario considerare percorsi arbitrari tra due nodi.
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 = 8Somma dei numeri dalla radice alle foglie
Sum root-to-leaf numbers (LeetCode #129) tratta ogni percorso dalla radice a una foglia come un numero decimale; ad esempio, il percorso 1→2→3 rappresenta il numero 123, e chiede di calcolarne la somma. Si costruisca il numero passando nella ricorsione current_number * 10 + node.val. A ogni foglia, si aggiunga il numero completato al totale. È un esempio chiaro di DFS pre-order che trasmette lo stato accumulato verso il basso.
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 = 1026Verifica 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: le varianti della somma dei percorsi (dalla radice a una foglia, tutti i percorsi, Path Sum III con somme prefisse), l’antenato comune più basso usando un’elegante suddivisione ricorsiva e l’LCA nei BST in O(log n) grazie alla proprietà di ordinamento. Ora inizieremo lo studio dei Binary Search Trees con le operazioni di inserimento e ricerca.
Domande Frequenti
La lezione «Somma dei percorsi e antenato comune più vicino» è gratuita?
Sì — il testo completo di «Somma dei percorsi e antenato comune più vicino» è 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 «Somma dei percorsi e antenato comune più vicino»?
Risolva root-to-leaf path sum, all-paths-sum e lowest-common-ancestor per un albero binario generico usando la discesa ricorsiva 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 4 di 4.
Quanto tempo richiede la lezione «Somma dei percorsi e antenato comune più vicino»?
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