Path sum en laagste gemeenschappelijke voorouder
Los root-to-leaf path sum, all-paths-sum en lowest-common-ancestor voor een algemene binaire boom op met recursieve afdaling.
Path sum en laagste gemeenschappelijke voorouder is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Padsom van wortel naar blad
Het padsomprobleem vraagt of er een pad van wortel naar blad is waarvan de som gelijk is aan een doelwaarde. Geef de resterende doelwaarde door tijdens de recursie en trek de waarde van elke knoop ervan af. Controleer bij een blad of de resterende waarde gelijk is aan de waarde van het blad. Zo hoef je geen expliciete padlijst bij te houden en blijft de oplossing zowel geheugenefficiënt als overzichtelijk. Randgeval: een lege boom heeft geen paden, dus geef onmiddellijk False terug.
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->2Alle paden van wortel naar blad
Als je alle paden wilt opsommen, houd je een lijst van het huidige pad bij. Voeg bij elke recursieve aanroep de waarde van de huidige knoop toe, roep de functie recursief aan voor de kinderen en voer bij terugkeer pop uit (ga één stap terug). Leg bij een blad een momentopname (list(path)) van het huidige pad vast. Dit patroon — kiezen, recursief aanroepen, keuze ongedaan maken — vormt de basis van terugzoeken in bomen.
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]]Padsom III: elk pad, elke knoop
Path Sum III (LeetCode #437) telt paden waarvan de som gelijk is aan een doelwaarde, waarbij het pad overal kan beginnen en eindigen (dus niet alleen bij wortel en blad). De brute-forceoplossing is O(n²): voer vanaf elke knoop een DFS uit. De optimale O(n)-aanpak gebruikt een hashmap met prefixsommen: houd de lopende som bij en tel hoe vaak current_sum - target eerder is voorgekomen, net als bij de aanpak voor sommen van deelarrays.
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)) # 3Wat is de laagste gemeenschappelijke voorouder?
De laagste gemeenschappelijke voorouder (LCA) van twee knopen p en q in een binaire boom is de diepste knoop die zowel p als q als afstammelingen heeft (een knoop kan een afstammeling van zichzelf zijn). Een LCA komt voor in problemen zoals ‘afstand tussen twee knopen’, ‘pad tussen twee knopen’ en bereikopvragingen in BST's. Inzicht in LCA is essentieel voor gevorderde boomproblemen.
# 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')Recursief LCA-algoritme
De elegante recursieve LCA-oplossing geeft de eerste knoop terug die p of q is, of beide in zijn deelbomen heeft. Als de huidige knoop p of q is, geef je die terug. Roep de functie anders recursief aan voor de linker- en rechterkant. Als beide kanten een niet-nullwaarde teruggeven, is de huidige knoop de LCA. Als slechts één kant een niet-nullwaarde teruggeeft, geef je dat resultaat naar boven door. Dit werkt in O(n) tijd en gebruikt O(h) ruimte.
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) # 3LCA wanneer een knoop zijn eigen voorouder kan zijn
Een belangrijk randgeval: als p een voorouder van q is (of andersom), is de LCA p zelf. Het recursieve algoritme handelt dit automatisch af: wanneer het p bereikt, geeft het p onmiddellijk terug, zonder in de deelbomen van p te kijken. De ouder ziet dan dat de ene kant p heeft teruggegeven en de andere kant null, en geeft p als de LCA naar boven door. Controleer dit geval altijd met je toets wanneer je LCA codeert.
# 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)LCA met ouderverwijzingen
Als elke knoop een ouderverwijzing heeft, wordt LCA een probleem van de ‘doorsnede van twee gelinkte lijsten’. Verzamel de voorouders van p in een verzameling en loop daarna vanaf q omhoog totdat je een knoop vindt die in die verzameling staat. Deze aanpak gebruikt O(h) tijd en O(h) ruimte en komt vaak voor bij sollicitatiegesprekken over systeemontwerp, waarbij je de structuur van knopen beheert en ouderverwijzingen kunt opslaan.
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')LCA in een binaire zoekboom
In een BST is LCA eenvoudiger, omdat de ordeningseigenschap aangeeft in welke deelboom elke knoop zich bevindt. Als p en q allebei kleiner zijn dan de huidige knoop, staat de LCA in de linker deelboom. Als beide groter zijn, staat de LCA in de rechter deelboom. In alle andere gevallen scheidt de huidige knoop ze, dus is die de LCA. Voor gebalanceerde BST's wordt het probleem hiermee teruggebracht tot 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')Afstand tussen twee knopen
De afstand tussen twee knopen in een boom is gelijk aan het aantal kanten op het pad dat ze verbindt. Je berekent dit rechtstreeks met de LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Zoek eerst de LCA en tel daarna de diepte van elke knoop. Met een goede hulpfunctie werkt dit in O(n) tijd en gebruikt het O(h) ruimte.
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)) # 2Pad van wortel naar blad met maximale som
Bij het pad van wortel naar blad met maximale som houd je de lopende som bij vanaf de wortel tot de huidige knoop. Vergelijk die bij bladeren met een globale maximumwaarde. Dit is een preorder-DFS waarbij de huidige padsom als parameter wordt doorgegeven. In tegenstelling tot de algemene maximale padsom is deze versie beperkt tot paden van wortel naar blad en daardoor eenvoudiger: je hoeft geen willekeurige paden van knoop naar knoop te overwegen.
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 = 8Getallen van wortel naar blad optellen
Bij getallen van wortel naar blad optellen (LeetCode #129) wordt elk pad van wortel naar blad beschouwd als een decimaal getal (bijvoorbeeld stelt pad 1→2→3 het getal 123 voor) en wordt naar de som daarvan gevraagd. Bouw het getal op door current_number * 10 + node.val door te geven tijdens de recursie. Voeg bij elk blad het voltooide getal toe aan het totaal. Dit is een duidelijk voorbeeld van preorder-DFS waarbij opgebouwde toestand naar beneden wordt doorgegeven.
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 = 1026Korte controle
Toets je begrip van de concepten uit Data Structures & Algorithms — Coding Interview Prep uit deze les.
Samenvatting van de les
In deze les heb je geleerd over varianten van padsommen (van wortel naar blad, alle paden en padsom III met prefixsommen), de laagste gemeenschappelijke voorouder met elegante recursieve opsplitsing en LCA in een BST in O(log n) dankzij de ordeningseigenschap. Hierna beginnen we met binaire zoekbomen en behandelen we invoeg- en zoekbewerkingen.
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Path sum en laagste gemeenschappelijke voorouder” gratis?
Ja — de volledige tekst van “Path sum en laagste gemeenschappelijke voorouder” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Path sum en laagste gemeenschappelijke voorouder”?
Los root-to-leaf path sum, all-paths-sum en lowest-common-ancestor voor een algemene binaire boom op met recursieve afdaling. Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Path sum en laagste gemeenschappelijke voorouder”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- TreeNode-klasse en BFS op niveaus
- In-order, pre-order en post-order DFS
- Diameter, hoogte en gebalanceerde bomen
- Path sum en laagste gemeenschappelijke voorouder