Forberedelse til kodeintervjuer · leksjon

Stisum og laveste felles forfader

Løs root-to-leaf path sum, all-paths-sum og lowest-common-ancestor for et generelt binærtre med rekursiv nedstigning.

Leksjon 4 av 413 trinn

Stisum og laveste felles forfader er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Stisum fra rot til blad

Problemet med stisum spør om det finnes en sti fra rot til blad som har en gitt målsum. Send gjenværende målsum ned gjennom rekursjonen, og trekk fra verdien til hver node. Ved et blad kontrollerer du om den gjenværende summen er lik verdien til bladet. Dette gjør at du slipper å vedlikeholde en eksplisitt stiliste, og løsningen bruker lite plass og er ryddig. Spesialtilfelle: Et tomt tre har ingen stier, så returner False umiddelbart.

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

Alle stier fra rot til blad

For å enumerere alle stier vedlikeholder du en løpende stiliste. Ved hvert rekursive kall legger du til verdien til den gjeldende noden, rekurserer til barna og utfører deretter pop ved retur (gå tilbake). Ved et blad lagrer du et øyeblikksbilde (list(path)) av den gjeldende stien. Dette mønsteret — velg, rekursér, velg bort — er grunnlaget for backtracking på trær.

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]]

Stisum III: Valgfri sti, valgfri node

Path Sum III (LeetCode #437) teller stier som har en gitt målsum, der stien kan starte og slutte hvor som helst (ikke bare fra rot til blad). En brute-force-løsning har O(n²): kjør en DFS fra hver node. Den optimale O(n)-tilnærmingen bruker et hash-kart for prefikssummer: følg med på den løpende summen og tell hvor mange ganger current_sum - target har forekommet tidligere, på samme måte som for tilnærmingen med subarray-summer.

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

Hva er laveste felles stamfar?

Den laveste felles stamfaren (LCA) til to noder p og q i et binært tre er den dypeste noden som har både p og q som etterkommere (en node kan være sin egen etterkommer). LCA dukker opp i problemer som «avstand mellom to noder», «sti mellom to noder» og intervallspørringer i BST-er. Å forstå LCA er avgjørende for viderekomne treproblemer.

#       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-algoritme

Den elegante rekursive LCA-løsningen returnerer den første noden som enten er p eller q, eller som har begge i undertrærne sine. Hvis den gjeldende noden er p eller q, returnerer du den. Ellers rekursérer du til venstre og høyre. Hvis begge sidene returnerer en verdi som ikke er null, er den gjeldende noden LCA-en. Hvis bare én side ikke er null, sender du dette resultatet videre oppover. Dette bruker O(n) tid og O(h) plass.

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 når en node kan være sin egen stamfar

Et viktig spesialtilfelle: Hvis p er en stamfar til q (eller omvendt), er LCA p selv. Den rekursive algoritmen håndterer dette automatisk — når den når p, returnerer den p umiddelbart uten å undersøke undertrærne til p. Forelderen ser at den ene siden returnerte p og den andre returnerte null, så den sender p videre oppover som LCA. Kontroller alltid dette tilfellet i testen din når du implementerer 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 pekere til forelder

Hvis hver node har en peker til forelderen, reduseres LCA til problemet med «skjæringspunktet mellom to lenkede lister». Samle forfedrene til p i en mengde, og gå deretter oppover fra q til du finner en node i mengden. Denne tilnærmingen bruker O(h) tid og O(h) plass og er vanlig i systemdesignintervjuer der du kontrollerer nodestrukturen og kan lagre foreldreferanser.

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 et binært søketre

I et BST er LCA enklere fordi ordensegenskapen forteller deg hvilket undertre hver node ligger i. Hvis både p og q er mindre enn den gjeldende noden, ligger LCA i det venstre undertreet. Hvis begge er større, ligger LCA i det høyre undertreet. Ellers skiller den gjeldende noden dem, og den er derfor LCA. Dette reduserer problemet til O(log n) for balanserte BST-er.

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')

Avstand mellom to noder

Avstanden mellom to noder i et tre er lik antallet kanter på stien som forbinder dem. Dette beregnes direkte fra LCA: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Finn først LCA-en, og tell deretter dybden til hver node. Med en god hjelpefunksjon bruker dette O(n) tid og O(h) plass.

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

Maksimal sum av sti fra rot til blad

Den maksimale stisummen fra rot til blad holder oversikt over den løpende summen fra roten til den gjeldende noden. Ved blader sammenligner du summen med en global maksimumsverdi. Dette er en pre-order-DFS der summen for den gjeldende stien sendes inn som en parameter. I motsetning til den generelle maksimale stisummen er denne varianten begrenset til stier fra rot til blad, så den er enklere — du trenger ikke ta hensyn til vilkårlige stier fra node til node.

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

Summer tall fra rot til blad

Summer tall fra rot til blad (LeetCode #129) behandler hver sti fra rot til blad som et desimaltall (for eksempel representerer stien 1→2→3 tallet 123) og ber om summen av disse tallene. Bygg tallet ved å sende current_number * 10 + node.val ned gjennom rekursjonen. Ved hvert blad legger du det ferdige tallet til totalen. Dette er et tydelig eksempel på pre-order-DFS som sender akkumulert tilstand nedover.

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

Hurtigsjekk

Test forståelsen din av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte du: varianter av stisum (fra rot til blad, alle stier og Path Sum III med prefikssummer), laveste felles stamfar ved hjelp av elegant rekursiv oppdeling, og BST-LCA i O(log n) ved hjelp av ordensegenskapen. Deretter begynner vi med binære søketrær og operasjoner for innsetting og søk.

Gratis å komme i gang

Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 90
Leksjoner: 360

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Stisum og laveste felles forfader» gratis?

Ja – hele teksten i «Stisum og laveste felles forfader» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva lærer jeg i «Stisum og laveste felles forfader»?

Løs root-to-leaf path sum, all-paths-sum og lowest-common-ancestor for et generelt binærtre med rekursiv nedstigning. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?

Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.

Hvor lang tid tar leksjonen «Stisum og laveste felles forfader»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?

Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

← Tilbake til Forberedelse til kodeintervjuer