Coding Interview Prep · Lekcja

Suma ścieżki i najniższy wspólny przodek

Lekcja 4 z 413 kroki

Suma ścieżki i najniższy wspólny przodek to bezpłatna lekcja Coding 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding 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->2

Wszystkie ś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))  # 3

Czym 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)  # 3

LCA, 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 = 8

Sumowanie 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 = 1026

Szybkie sprawdzenie

Proszę sprawdzić, czy rozumieją Państwo zagadnienia z kursu Data Structures & Algorithms — Coding Interview Prep omówione w tej lekcji.

Odpowiedz w interaktywnej 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.

Bezpłatny start

Ucz się Coding Interview Prep 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: 90
Lekcje: 360

Zacznij naukę bezpłatnie Wyświetl pełny kurs

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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding 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 Coding 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ąć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding 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 Coding Interview Prep?

Tak. Każda lekcja Coding 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

← Powrót do Coding Interview Prep