Pfadsumme und niedrigster gemeinsamer Vorfahr
Lösen Sie root-to-leaf path sum, all-paths-sum und lowest-common-ancestor für einen allgemeinen Binärbaum mit rekursivem Abstieg.
Pfadsumme und niedrigster gemeinsamer Vorfahr ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 4 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Pfadsumme von der Wurzel zum Blatt
Beim Pfadsummenproblem soll ermittelt werden, ob die Summe eines Pfades von der Wurzel zu einem Blatt einem Zielwert entspricht. Übergeben Sie das verbleibende Ziel in der Rekursion nach unten und subtrahieren Sie dabei den Wert jedes Knotens. Prüfen Sie an einem Blatt, ob der verbleibende Wert dem Wert des Blattes entspricht. So müssen Sie keine explizite Pfadliste verwalten, was sowohl speichereffizient als auch übersichtlich ist. Sonderfall: Ein leerer Baum enthält keine Pfade, daher geben Sie sofort False zurück.
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 Pfade von der Wurzel zum Blatt
Um alle Pfade aufzuzählen, verwalten Sie eine Pfadliste, die schrittweise aufgebaut wird. Hängen Sie bei jedem rekursiven Aufruf den Wert des aktuellen Knotens an, rufen Sie die Kinder rekursiv auf und führen Sie beim Zurückkehren ein pop aus (Backtracking). Speichern Sie an einem Blatt eine Momentaufnahme (list(path)) des aktuellen Pfades. Dieses Muster – auswählen, rekursiv aufrufen, Auswahl rückgängig machen – bildet die Grundlage für Backtracking bei Bäumen.
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]]Pfadsumme III: Jeder Pfad, jeder Knoten
Path Sum III (LeetCode #437) zählt Pfade, deren Summe einem Zielwert entspricht, wobei der Pfad an beliebiger Stelle beginnen und enden kann (also nicht nur an der Wurzel oder einem Blatt). Die Brute-Force-Lösung hat eine Laufzeit von O(n²): Sie führt von jedem Knoten aus eine DFS durch. Der optimale Ansatz mit O(n) verwendet eine Hashmap für Präfixsummen: Verfolgen Sie die laufende Summe und zählen Sie, wie oft current_sum - target zuvor aufgetreten ist – analog zum Ansatz für die Summe von Teilarrays.
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)) # 3Was ist der niedrigste gemeinsame Vorfahr?
Der niedrigste gemeinsame Vorfahr (Lowest Common Ancestor, LCA) zweier Knoten p und q in einem Binärbaum ist der tiefste Knoten, der sowohl p als auch q als Nachkommen hat (ein Knoten kann sein eigener Nachkomme sein). Der LCA kommt in Problemen wie „Abstand zwischen zwei Knoten“, „Pfad zwischen zwei Knoten“ und Bereichsabfragen in BSTs vor. Das Verständnis des LCA ist für fortgeschrittene Baumprobleme unerlässlich.
# 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')Rekursiver LCA-Algorithmus
Die elegante rekursive Lösung für den LCA gibt den ersten Knoten zurück, der entweder p oder q ist oder beide Knoten in seinen Teilbäumen enthält. Wenn der aktuelle Knoten p oder q ist, geben Sie ihn zurück. Andernfalls führen Sie die Rekursion links und rechts aus. Wenn beide Seiten einen Nicht-Null-Wert zurückgeben, ist der aktuelle Knoten der LCA. Wenn nur eine Seite einen Nicht-Null-Wert zurückgibt, geben Sie dieses Ergebnis nach oben weiter. Die Laufzeit beträgt O(n), der Speicherbedarf O(h).
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, wenn ein Knoten sein eigener Vorfahr sein kann
Ein wichtiger Sonderfall: Wenn p ein Vorfahr von q ist (oder umgekehrt), ist der LCA p selbst. Der rekursive Algorithmus behandelt dies automatisch: Sobald er p erreicht, gibt er p sofort zurück, ohne die Teilbäume von p zu untersuchen. Der Elternknoten sieht dann, dass eine Seite p und die andere Seite null zurückgegeben hat, und gibt p als LCA nach oben weiter. Überprüfen Sie diesen Fall beim Implementieren eines LCA immer mit einem 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)LCA mit Elternzeigern
Wenn jeder Knoten einen Elternzeiger besitzt, reduziert sich der LCA auf das Problem der „Schnittmenge zweier verketteter Listen“. Sammeln Sie die Vorfahren von p in einer Menge und gehen Sie anschließend von q aus nach oben, bis Sie einen Knoten aus dieser Menge finden. Dieser Ansatz mit O(h) Laufzeit und O(h) Speicherplatz ist in Systemdesign-Interviews üblich, wenn Sie die Knotenstruktur selbst festlegen und Elternreferenzen speichern können.
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 einem binären Suchbaum
In einem BST ist der LCA einfacher zu bestimmen, weil die Ordnungseigenschaft vorgibt, in welchem Teilbaum sich jeder Knoten befindet. Wenn p und q beide kleiner als der aktuelle Knoten sind, liegt der LCA im linken Teilbaum. Wenn beide größer sind, liegt er im rechten Teilbaum. Andernfalls trennt der aktuelle Knoten die beiden Knoten, ist also der LCA. Bei ausgeglichenen BSTs reduziert sich die Laufzeit dadurch auf 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')Abstand zwischen zwei Knoten
Der Abstand zwischen zwei Knoten in einem Baum entspricht der Anzahl der Kanten auf dem sie verbindenden Pfad. Er lässt sich direkt anhand des LCA berechnen: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Ermitteln Sie zuerst den LCA und anschließend die Tiefe jedes Knotens. Mit einem geeigneten Hilfsverfahren beträgt die Laufzeit O(n) und der Speicherbedarf O(h).
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)) # 2Maximale Pfadsumme von der Wurzel zum Blatt
Bei der maximalen Pfadsumme von der Wurzel zum Blatt wird die laufende Summe von der Wurzel bis zum aktuellen Knoten verfolgt. Vergleichen Sie an Blättern die Summe mit einem globalen Maximum. Dies ist eine Preorder-DFS, bei der die aktuelle Pfadsumme als Parameter übergeben wird. Im Gegensatz zur allgemeinen maximalen Pfadsumme ist diese Variante auf Pfade von der Wurzel zu einem Blatt beschränkt und daher einfacher – beliebige Pfade von Knoten zu Knoten müssen nicht berücksichtigt werden.
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 = 8Zahlen von der Wurzel zum Blatt summieren
Sum root-to-leaf numbers (LeetCode #129) interpretiert jeden Pfad von der Wurzel zu einem Blatt als Dezimalzahl (der Pfad 1→2→3 entspricht beispielsweise der Zahl 123) und verlangt deren Summe. Bauen Sie die Zahl auf, indem Sie current_number * 10 + node.val in der Rekursion nach unten übergeben. Addieren Sie an jedem Blatt die fertige Zahl zur Gesamtsumme. Dies ist ein anschauliches Beispiel für eine Preorder-DFS, bei der angesammelter Zustand nach unten weitergegeben wird.
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 = 1026Kurze Überprüfung
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie Folgendes gelernt: Varianten von Pfadsummen (von der Wurzel zum Blatt, alle Pfade, Path Sum III mit Präfixsummen), den niedrigsten gemeinsamen Vorfahren mithilfe einer eleganten rekursiven Aufteilung sowie den LCA in einem BST in O(log n) unter Verwendung der Ordnungseigenschaft. Als Nächstes beginnen wir mit binären Suchbäumen und behandeln Einfüge- und Suchoperationen.
Häufig gestellte Fragen
Ist die Lektion „Pfadsumme und niedrigster gemeinsamer Vorfahr“ kostenlos?
Ja — der vollständige Text von „Pfadsumme und niedrigster gemeinsamer Vorfahr“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Pfadsumme und niedrigster gemeinsamer Vorfahr“?
Lösen Sie root-to-leaf path sum, all-paths-sum und lowest-common-ancestor für einen allgemeinen Binärbaum mit rekursivem Abstieg. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 4 von 4.
Wie lange dauert die Lektion „Pfadsumme und niedrigster gemeinsamer Vorfahr“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- TreeNode-Klasse und BFS nach Ebenen
- In-Order-, Pre-Order- und Post-Order-DFS
- Durchmesser, Höhe und balancierte Bäume
- Pfadsumme und niedrigster gemeinsamer Vorfahr