Valmistautuminen ohjelmointihaastatteluihin · Oppitunti

Polkusumma ja pienin yhteinen esivanhempi

Ratkaiskaa juuresta lehteen kulkevan polun summa, kaikkien polkujen summa ja yleisen binääripuun pienin yhteinen esivanhempi rekursiivisella läpikäynnillä.

Oppitunti 4/413 vaihetta

Polkusumma ja pienin yhteinen esivanhempi on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Juuresta lehteen kulkevan polun summa

Polkusummaongelmassa selvitetään, onko jonkin juuresta lehteen kulkevan polun summa tavoitteen suuruinen. Välittäkää rekursiossa alaspäin jäljellä oleva tavoitesumma ja vähentäkää siitä kunkin solmun arvo. Tarkistakaa lehdessä, onko jäljellä oleva summa sama kuin lehden arvo. Näin vältetään erillisen polkulistan ylläpitäminen, ja ratkaisu on sekä tilankäytöltään tehokas että selkeä. Erityistapaus: tyhjellä puulla ei ole polkuja, joten palauttakaa heti 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

Kaikki juuresta lehteen kulkevat polut

Kaikkien polkujen luettelemiseksi ylläpidetään juoksevaa polkulistaa. Lisätkää kunkin rekursiivisen kutsun alussa nykyisen solmun arvo listaan, kutsukaa rekursiota lapsille ja tehkää palatessa pop (peruutusaskel). Tallentakaa lehdessä nykyisestä polusta tilannevedos (list(path)). Tämä kuvio — valitse, kutsu rekursiota, peru valinta — on puissa tehtävän peruutushaun perusta.

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

Polkusumma III: mikä tahansa polku, mikä tahansa solmu

Polkusumma III (LeetCode #437) laskee niiden polkujen määrän, joiden summa on tavoitteen suuruinen ja jotka voivat alkaa ja päättyä missä tahansa kohdissa puuta, eivät vain juuressa ja lehdessä. Raakavoimainen ratkaisu on O(n²): suoritetaan DFS jokaisesta solmusta. Optimaalisessa O(n)-ratkaisussa käytetään prefiksisummien hajautustaulua: seurataan juoksevaa summaa ja lasketaan, kuinka monta kertaa current_sum - target on esiintynyt aiemmin. Tämä vastaa osataulukoiden summien käsittelytapaa.

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

Mikä on lähin yhteinen esi-isä?

Kahden binääripuun solmun p ja q lähin yhteinen esi-isä (LCA) on syvimmällä oleva solmu, jonka jälkeläisiä sekä p että q ovat. Solmu voi olla myös itsensä jälkeläinen. LCA:ta tarvitaan esimerkiksi ongelmissa, joissa lasketaan kahden solmun välinen etäisyys tai polku, sekä binäärihakupuun aluekyselyissä. LCA:n ymmärtäminen on olennaista keskitason puuongelmissa.

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

Rekursiivinen LCA-algoritmi

Tyylikäs rekursiivinen LCA-ratkaisu palauttaa ensimmäisen solmun, joka on joko p tai q tai jonka molemmissa osapuissa p ja q ovat. Jos nykyinen solmu on p tai q, palauttakaa se. Muussa tapauksessa kutsukaa rekursiota vasemmassa ja oikeassa osapuussa. Jos molemmat puolet palauttavat ei-null-arvon, nykyinen solmu on LCA. Jos vain toinen puoli palauttaa ei-null-arvon, välittäkää kyseinen tulos ylöspäin. Aikavaativuus on O(n) ja tilavaativuus 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)  # 3

LCA, kun solmu voi olla oma esi-isänsä

Kriittinen erityistapaus: jos p on q:n esi-isä tai päinvastoin, LCA on p itse. Rekursiivinen algoritmi käsittelee tämän automaattisesti — kun se saavuttaa p:n, se palauttaa p:n välittömästi tutkimatta p:n osapuita. Vanhempi näkee, että toinen puoli palautti p:n ja toinen null-arvon, joten se välittää p:n ylöspäin LCA:na. Varmistakaa tämä tapaus aina testillä, kun toteutatte LCA:n.

# 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 vanhemmuusosoittimien avulla

Jos jokaisella solmulla on vanhemmuusosoitin, LCA-ongelma pelkistyy kahden linkitetyn listan leikkauskohdan etsimiseksi. Kerätkää p:n esi-isät joukkoon ja kulkekaa sitten q:sta ylöspäin, kunnes löydätte joukkoon kuuluvan solmun. Tämä O(h)-aikainen ja O(h)-tilaa käyttävä lähestymistapa on yleinen järjestelmähaastatteluissa, joissa hallitsette solmurakennetta ja voitte tallentaa vanhemmuusviittauksia.

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 binäärihakupuussa

Binäärihakupuussa LCA on yksinkertaisempi, koska järjestysominaisuus kertoo, missä osapuussa kukin solmu sijaitsee. Jos sekä p että q ovat nykyistä solmua pienempiä, LCA on vasemmassa osapuussa. Jos molemmat ovat suurempia, LCA on oikeassa osapuussa. Muussa tapauksessa nykyinen solmu jakaa ne eri puolille, joten se on LCA. Tasapainotetuissa binäärihakupuissa tämä pienentää aikavaativuuden arvoon 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')

Kahden solmun välinen etäisyys

Puun kahden solmun välinen etäisyys on niitä yhdistävän polun särmien määrä. Se voidaan laskea suoraan LCA:n avulla: distance(p, q) = depth(p) + depth(q) - 2 * depth(LCA(p,q)). Etsikää ensin LCA ja laskekaa sitten kummankin solmun syvyys. Sopivan apufunktion avulla aikavaativuus on O(n) ja tilavaativuus 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))  # 2

Juuresta lehteen kulkevan polun suurin summa

Juuresta lehteen kulkevan polun suurimmassa summassa seurataan juuresta nykyiseen solmuun kulkevan polun juoksevaa summaa. Lehdissä sitä verrataan globaaliin maksimiin. Kyseessä on etujärjestyksen DFS-läpikäynti, jossa nykyinen polkusumma välitetään parametrina. Toisin kuin yleisessä polun maksimisummassa, tässä versiossa huomioidaan vain juuresta lehteen kulkevat polut, joten se on yksinkertaisempi — mielivaltaisia solmusta solmuun kulkevia polkuja ei tarvitse käsitellä.

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

Juuresta lehteen muodostuvien lukujen summa

Juuresta lehteen muodostuvien lukujen summa (LeetCode #129) käsittelee jokaista juuresta lehteen kulkevaa polkua desimaalilukuna (esimerkiksi polku 1→2→3 edustaa lukua 123) ja pyytää laskemaan näiden summan. Muodostakaa luku välittämällä rekursiossa alaspäin current_number * 10 + node.val. Lisätkää valmis luku jokaisessa lehdessä kokonaissummaan. Tämä on selkeä esimerkki etujärjestyksen DFS-läpikäynnistä, jossa kertynyt tila välitetään alaspäin.

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

Pikatarkistus

Testatkaa ymmärrystänne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheista.

Vastaa interaktiivisessa oppitunnissa

Oppitunnin kertaus

Tässä oppitunnissa opitte polkusumman muunnelmat (juuresta lehteen kulkevat polut, kaikki polut ja prefiksisummia käyttävä polkusumma III), lähimmän yhteisen esi-isän löytämisen tyylikkään rekursiivisen jaon avulla sekä binäärihakupuun LCA:n löytämisen järjestysominaisuutta hyödyntäen ajassa O(log n). Seuraavaksi aloitamme binäärihakupuihin tutustumisen lisäämis- ja hakutoiminnoilla.

Aloita maksutta

Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi

Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.

Kurssit: 90
Oppitunnit: 360

Aloita opiskelu maksutta Näytä koko kurssi

Usein kysytyt kysymykset

Onko oppitunti ”Polkusumma ja pienin yhteinen esivanhempi” ilmainen?

Kyllä – oppitunnin ”Polkusumma ja pienin yhteinen esivanhempi” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.

Mitä opin oppitunnilla ”Polkusumma ja pienin yhteinen esivanhempi”?

Ratkaiskaa juuresta lehteen kulkevan polun summa, kaikkien polkujen summa ja yleisen binääripuun pienin yhteinen esivanhempi rekursiivisella läpikäynnillä. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.

Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?

Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.

Kuinka kauan ”Polkusumma ja pienin yhteinen esivanhempi”-oppitunnin suorittaminen kestää?

Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.

Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?

Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.

Kaikki tämän kurssin oppitunnit

TreeNode-luokka ja tasojärjestyksen BFS
In-order-, pre-order- ja post-order-DFS
Halkaisija, korkeus ja tasapainotetut puut
Polkusumma ja pienin yhteinen esivanhempi

← Takaisin: Valmistautuminen ohjelmointihaastatteluihin