Summor av vägar och närmaste gemensamma förfader
Lös root-to-leaf path sum, all-paths-sum och lowest-common-ancestor för ett allmänt binärt träd med rekursiv nedstigning.
Summor av vägar och närmaste gemensamma förfader är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Pathsumma från rot till löv
Pathsummeproblemet frågar om någon väg från rot till löv har en summa som motsvarar ett målvärde. Skicka med det återstående målvärdet i rekursionen och subtrahera varje nods värde. Kontrollera vid ett löv om det återstående värdet är lika med lövets värde. På så sätt behöver du inte underhålla en explicit lista över vägen, och lösningen blir både minneseffektiv och tydlig. Ett specialfall är ett tomt träd: det har inga vägar, så returnera False direkt.
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->2Alla vägar från rot till löv
För att generera alla vägar underhåller du en lista över den aktuella vägen. Vid varje rekursivt anrop lägger du till den aktuella nodens värde, anropar rekursionen för barnen och gör sedan pop när anropet returnerar (backtracking). Vid ett löv sparar du en ögonblicksbild (list(path)) av den aktuella vägen. Detta mönster – välj, rekursivt anrop, välj bort – är grunden för backtracking i träd.
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: Valfri väg, valfri nod
Path Sum III (LeetCode #437) räknar vägar vars summa motsvarar ett målvärde, där vägen kan börja och sluta var som helst (inte bara från rot till löv). En brute force-lösning har komplexiteten O(n²): kör en DFS från varje nod. Den optimala lösningen med O(n) använder en hashkarta med prefixsummor: spåra den löpande summan och räkna hur många gånger current_sum - target har förekommit tidigare, på samma sätt som i problemet med delarray-summor.
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)) # 3Vad är den lägsta gemensamma förfadern?
Den lägsta gemensamma förfadern (LCA) till två noder p och q i ett binärt träd är den djupaste nod som har både p och q som ättlingar (en nod kan vara ättling till sig själv). LCA förekommer i problem som ”avståndet mellan två noder”, ”vägen mellan två noder” och intervallfrågor i BST. Att förstå LCA är viktigt för trädproblem på mellannivå.
# 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')Rekursiv LCA-algoritm
Den eleganta rekursiva LCA-lösningen returnerar den första nod som antingen är p eller q, eller som har båda i sina delträd. Om den aktuella noden är p eller q returnerar du den. Annars anropar du rekursionen för vänster och höger delträd. Om båda sidor returnerar ett värde som inte är null är den aktuella noden LCA. Om bara en sida returnerar ett värde som inte är null skickar du det resultatet vidare uppåt. Komplexiteten är O(n) i tid och O(h) i minne.
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 när en nod kan vara sin egen förfader
Ett viktigt specialfall är när p är förfader till q (eller tvärtom): då är LCA p själv. Den rekursiva algoritmen hanterar detta automatiskt – när den når p returnerar den p direkt utan att undersöka p:s delträd. Föräldern ser då att den ena sidan returnerade p och den andra null, och skickar därför p vidare uppåt som LCA. Kontrollera alltid detta fall i dina tester när du implementerar LCA.
# 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 med pekare till förälder
Om varje nod har en pekare till föräldern blir LCA-problemet en variant av problemet med ”snittet mellan två länkade listor”. Samla p:s förfäder i en mängd och gå sedan uppåt från q tills du hittar en nod som finns i mängden. Denna metod har komplexiteten O(h) i tid och O(h) i minne och är vanlig i intervjuer om systemdesign, där du själv bestämmer nodstrukturen och kan lagra referenser till föräldrar.
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 i ett binärt sökträd
I ett BST är LCA enklare, eftersom ordningsegenskapen visar vilket delträd som innehåller respektive nod. Om både p och q är mindre än den aktuella noden finns LCA i det vänstra delträdet. Om båda är större finns LCA i det högra delträdet. Annars delar den aktuella noden upp dem, och är därför LCA. För balanserade BST:er minskar detta problemets komplexitet till 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')Avståndet mellan två noder
Avståndet mellan två noder i ett träd är lika med antalet kanter på vägen som förbinder dem. Det beräknas direkt med hjälp av LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Hitta först LCA och räkna sedan djupet för varje nod. Med en lämplig hjälpfunktion blir komplexiteten O(n) i tid och O(h) i minne.
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)) # 2Maximal summa på en väg från rot till löv
Den maximala summan på en väg från rot till löv spårar den löpande summan från roten till den aktuella noden. Vid löv jämför du summan med ett globalt maximum. Detta är en pre-order-DFS där current-path-sum skickas med som parameter. Till skillnad från den allmänna maximala pathsumman är denna variant begränsad till vägar från rot till löv och är därför enklare – du behöver inte ta hänsyn till godtyckliga vägar från nod till nod.
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 = 8Summera tal från rot till löv
Summera tal från rot till löv (LeetCode #129) behandlar varje väg från rot till löv som ett decimaltal (t.ex. representerar vägen 1→2→3 talet 123) och ber dig beräkna deras summa. Bygg talet genom att skicka ned current_number * 10 + node.val i rekursionen. Lägg vid varje löv till det färdiga talet till totalsumman. Detta är ett tydligt exempel på pre-order-DFS där ackumulerat tillstånd skickas nedåt.
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 = 1026Snabbtest
Testa din förståelse av begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen lärde du dig: varianter av pathsumma (från rot till löv, alla vägar och Path Sum III med prefixsummor), lägsta gemensamma förfader med elegant rekursiv uppdelning och LCA i BST i O(log n) med hjälp av ordningsegenskapen. Härnäst börjar vi med binära sökträd och operationerna infogning och sökning.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Summor av vägar och närmaste gemensamma förfader” gratis?
Ja – hela texten till ”Summor av vägar och närmaste gemensamma förfader” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Summor av vägar och närmaste gemensamma förfader”?
Lös root-to-leaf path sum, all-paths-sum och lowest-common-ancestor för ett allmänt binärt träd med rekursiv nedstigning. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Summor av vägar och närmaste gemensamma förfader”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- TreeNode-klassen och BFS nivå för nivå
- In-order, pre-order och post-order DFS
- Diameter, höjd och balanserade träd
- Summor av vägar och närmaste gemensamma förfader