Suma ścieżki i najniższy wspólny przodek
Rozwiążą Państwo problemy sumy ścieżki od korzenia do liścia, sum wszystkich ścieżek i najniższego wspólnego przodka dla dowolnego drzewa binarnego, stosując rekurencyjne przechodzenie w dół.
Suma ścieżki i najniższy wspólny przodek to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Suma ścieżki od korzenia do liścia
Problem sumy ścieżki polega na sprawdzeniu, czy istnieje ścieżka od korzenia do liścia, której suma jest równa wartości docelowej. Należy przekazywać w dół rekurencji pozostałą wartość docelową, odejmując wartość każdego węzła. W liściu należy sprawdzić, czy pozostała wartość docelowa jest równa wartości tego liścia. Dzięki temu nie trzeba przechowywać jawnej listy ścieżki, a rozwiązanie jest zarówno oszczędne pamięciowo, jak i przejrzyste. Przypadek brzegowy: puste drzewo nie zawiera żadnych ścieżek, więc należy natychmiast zwrócić 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->2Wszystkie ścieżki od korzenia do liścia
Aby wyliczyć wszystkie ścieżki, należy przechowywać listę aktualnej ścieżki. W każdym wywołaniu rekurencyjnym trzeba dodać wartość bieżącego węzła, wywołać rekurencję dla jego dzieci, a następnie przy powrocie wykonać operację pop (cofnąć wybór). W liściu należy zapisać kopię (list(path)) bieżącej ścieżki. Ten wzorzec — wybierz, wykonaj rekurencję, cofnij wybór — stanowi podstawę algorytmów backtrackingu na drzewach.
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]]Suma ścieżki III: dowolna ścieżka, dowolny węzeł
Path Sum III (LeetCode #437) zlicza ścieżki, których suma jest równa wartości docelowej, przy czym ścieżka może zaczynać się i kończyć w dowolnym miejscu, a nie tylko w korzeniu i liściu. Rozwiązanie siłowe ma złożoność O(n²): uruchamia DFS z każdego węzła. Optymalne rozwiązanie o złożoności O(n) wykorzystuje mapę haszującą sum prefiksowych: śledzi bieżącą sumę i zlicza, ile razy wcześniej wystąpiła wartość current_sum - target, podobnie jak w podejściu opartym na sumie podtablicy.
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)) # 3Czym jest najniższy wspólny przodek?
Najniższy wspólny przodek (LCA) dwóch węzłów p i q w drzewie binarnym to najgłębszy węzeł, który ma zarówno p, jak i q wśród swoich potomków, przy czym węzeł może być potomkiem samego siebie. LCA pojawia się w problemach takich jak „odległość między dwoma węzłami”, „ścieżka między dwoma węzłami” oraz zapytania o zakres w BST. Zrozumienie LCA jest niezbędne przy rozwiązywaniu średnio zaawansowanych problemów dotyczących drzew.
# 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')Rekurencyjny algorytm LCA
Eleganckie rekurencyjne rozwiązanie problemu LCA zwraca pierwszy węzeł, który jest węzłem p lub q albo ma oba te węzły w swoich poddrzewach. Jeśli bieżący węzeł jest równy p lub q, należy go zwrócić. W przeciwnym razie trzeba rekurencyjnie przeszukać lewe i prawe poddrzewo. Jeśli oba wywołania zwrócą wartość inną niż null, bieżący węzeł jest LCA. Jeśli tylko jedna strona zwróci wartość inną niż null, należy przekazać ten wynik wyżej. Algorytm działa w czasie O(n) i zużywa O(h) pamięci.
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, gdy węzeł może być własnym przodkiem
Istotny przypadek brzegowy: jeśli p jest przodkiem q (lub odwrotnie), LCA jest równy p. Algorytm rekurencyjny obsługuje to automatycznie — po dotarciu do p natychmiast zwraca p, bez zaglądania do poddrzew p. Rodzic zobaczy, że jedna strona zwróciła p, a druga null, więc przekaże p wyżej jako LCA. Podczas implementowania LCA zawsze należy uwzględnić ten przypadek w testach.
# 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 ze wskaźnikami do rodzica
Jeśli każdy węzeł ma wskaźnik do rodzica, problem LCA sprowadza się do problemu „przecięcia dwóch list połączonych”. Należy zebrać przodków p w zbiorze, a następnie przechodzić w górę od q, aż zostanie znaleziony węzeł należący do tego zbioru. To podejście o czasie O(h) i pamięci O(h) jest często spotykane podczas rozmów rekrutacyjnych dotyczących projektowania systemów, gdy można kontrolować strukturę węzłów i przechowywać odwołania do rodziców.
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 w drzewie wyszukiwania binarnego
W BST wyznaczenie LCA jest prostsze, ponieważ własność porządku wskazuje, w którym poddrzewie znajduje się każdy z węzłów. Jeśli zarówno p, jak i q są mniejsze od bieżącego węzła, LCA znajduje się w lewym poddrzewie. Jeśli oba są większe, LCA znajduje się w prawym poddrzewie. W przeciwnym razie bieżący węzeł rozdziela je, więc jest ich LCA. W przypadku zrównoważonych drzew BST redukuje to złożoność problemu do 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')Odległość między dwoma węzłami
Odległość między dwoma węzłami w drzewie jest równa liczbie krawędzi na łączącej je ścieżce. Można ją bezpośrednio obliczyć na podstawie LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Najpierw należy znaleźć LCA, a następnie głębokość każdego węzła. Przy użyciu odpowiedniej funkcji pomocniczej algorytm działa w czasie O(n) i zużywa O(h) pamięci.
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)) # 2Ścieżka o maksymalnej sumie od korzenia do liścia
Ścieżka od korzenia do liścia o maksymalnej sumie śledzi bieżącą sumę od korzenia do aktualnego węzła. W liściach należy porównać ją z globalną wartością maksymalną. Jest to przeszukiwanie DFS w porządku preorder, w którym bieżąca suma ścieżki jest przekazywana jako parametr. W przeciwieństwie do ogólnego problemu maksymalnej sumy ścieżki, ta wersja ogranicza się do ścieżek od korzenia do liścia, więc jest prostsza — nie trzeba uwzględniać dowolnych ścieżek między węzłami.
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 = 8Sumowanie liczb od korzenia do liścia
Sumowanie liczb od korzenia do liścia (LeetCode #129) traktuje każdą ścieżkę od korzenia do liścia jako liczbę dziesiętną, na przykład ścieżka 1→2→3 oznacza liczbę 123, i zwraca sumę tych liczb. Liczbę należy tworzyć, przekazując w dół rekurencji wartość current_number * 10 + node.val. W każdym liściu trzeba dodać ukończoną liczbę do sumy całkowitej. Jest to przejrzysty przykład przeszukiwania DFS w porządku preorder z przekazywaniem zgromadzonego stanu w dół.
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 = 1026Szybkie sprawdzenie
Proszę sprawdzić, czy rozumieją Państwo zagadnienia z kursu Data Structures & Algorithms — Coding Interview Prep omówione w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo: wariantów problemu sumy ścieżki (od korzenia do liścia, wszystkie ścieżki, Path Sum III z sumami prefiksowymi), najniższego wspólnego przodka wyznaczanego za pomocą eleganckiego rekurencyjnego podziału oraz LCA w BST w czasie O(log n), wykorzystującego własność porządku. Następnie rozpoczniemy temat drzew wyszukiwania binarnego od operacji wstawiania i wyszukiwania.
Ucz się Python dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 30
- Lekcje
- 120
Często zadawane pytania
Czy lekcja „Suma ścieżki i najniższy wspólny przodek” jest bezpłatna?
Tak — pełny tekst „Suma ścieżki i najniższy wspólny przodek” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Suma ścieżki i najniższy wspólny przodek”?
Rozwiążą Państwo problemy sumy ścieżki od korzenia do liścia, sum wszystkich ścieżek i najniższego wspólnego przodka dla dowolnego drzewa binarnego, stosując rekurencyjne przechodzenie w dół. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Suma ścieżki i najniższy wspólny przodek”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Klasa TreeNode i BFS poziomami
- DFS w kolejności inorder, preorder i postorder
- Średnica, wysokość i drzewa zrównoważone
- Suma ścieżki i najniższy wspólny przodek