K:nneksi pienin, alueen summa ja BST järjestetyksi taulukoksi
Hyödyntäkää järjestettyä in-order-läpikäyntiä löytääksenne k:nneksi pienimmän alkion ajassa O(k) ja laskeaksenne alueelle sijoittuvien arvojen summan ajassa O(log n + k).
K:nneksi pienin, alueen summa ja BST järjestetyksi taulukoksi 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.
K:nneksi pienin alkio BST:ssä
Kth Smallest Element in a BST (LeetCode #230) on klassinen tehtävä, joka hyödyntää suoraan lajiteltua in-order-läpikäyntiä. Koska in-order-läpikäynti käsittelee solmut kasvavassa järjestyksessä, laskemme solmuja läpikäynnin aikana ja palautamme arvon kohdassa k. Aikavaativuus on O(h + k), missä h on korkeus (vasemmanpuoleiseen solmuun pääsemiseksi) ja k on in-order-läpikäynnin askelten määrä.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def kth_smallest(root, k):
count = [0]
result = [None]
def inorder(node):
if not node or result[0] is not None:
return
inorder(node.left)
count[0] += 1
if count[0] == k:
result[0] = node.val
return
inorder(node.right)
inorder(root)
return result[0]
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_smallest(root, 1)) # 1
print(kth_smallest(root, 2)) # 2K:nneksi pienin: iteratiivinen toteutus pinon avulla
Iteratiivinen versio käyttää eksplisiittiseen pinoon perustuvaa in-order-mallia. Työntäkää vasemmanpuoleisia solmuja pinoon, kunnes saavutetaan null, ja poistakaa sitten solmu pinosta sekä kasvattakaa laskuria. Kun laskuri saavuttaa arvon k, palauttakaa nykyisen solmun arvo. Tämä välttää Pythonin rekursiorajan hyvin syvissä puissa, ja aikavaativuus on edelleen O(h + k) sekä tilavaativuus O(h). Haastattelijat pyytävät usein iteratiivista versiota rekursiivisen version jälkeen.
def kth_smallest_iterative(root, k):
stack = []
curr = root
count = 0
while curr or stack:
while curr: # go as far left as possible
stack.append(curr)
curr = curr.left
curr = stack.pop() # process node
count += 1
if count == k:
return curr.val
curr = curr.right # move to right subtree
return -1 # k out of range
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(2)
root.left.right = TreeNode(4)
root.left.left.left = TreeNode(1)
print(kth_smallest_iterative(root, 3)) # 3K:nneksi suurin alkio BST:ssä
Kth Largest käyttää käänteistä in-order-läpikäyntiä (oikea → juuri → vasen), joka käsittelee solmut laskevassa järjestyksessä. Laskekaa k askelta ja palauttakaa nykyisen solmun arvo. Tämä on symmetrinen k:nneksi pienimmän alkion etsimiseen nähden, ja sen aikavaativuus on O(h + k). Vaihtoehtoisesti voitte laskea arvon kth_smallest(root, total_count - k + 1), jos puun koko tunnetaan, mutta käänteiseen in-order-läpikäyntiin perustuva lähestymistapa on elegantimpi.
def kth_largest(root, k):
count = [0]
result = [None]
def reverse_inorder(node):
if not node or result[0] is not None:
return
reverse_inorder(node.right) # visit LARGER values first
count[0] += 1
if count[0] == k:
result[0] = node.val
return
reverse_inorder(node.left)
reverse_inorder(root)
return result[0]
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.left.right = TreeNode(2)
print(kth_largest(root, 1)) # 4 (largest)
print(kth_largest(root, 2)) # 3 (2nd largest)BST:n arvojen summa välillä
Range Sum of BST (LeetCode #938) pyytää laskemaan kaikkien välille [low, high] kuuluvien arvojen summan. Hyödyntäkää BST:n ominaisuutta haarojen karsimiseen: jos nykyisen solmun arvo on pienempi kuin low, koko vasen alipuu on niin ikään low-arvon alapuolella — ohittakaa se. Jos nykyinen arvo on suurempi kuin high, ohittakaa oikea alipuu. Näin voidaan karsia monia haaroja, ja ratkaisu on tehokkaampi kuin koko in-order-läpikäynti.
def range_sum_bst(root, low, high):
if not root:
return 0
total = 0
if low <= root.val <= high:
total += root.val
if root.val > low: # left subtree might have values >= low
total += range_sum_bst(root.left, low, high)
if root.val < high: # right subtree might have values <= high
total += range_sum_bst(root.right, low, high)
return total
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(range_sum_bst(root, 7, 15)) # 7+10+15 = 32Väliin kuuluvien solmujen laskeminen
Välille [low, high] kuuluvien solmujen laskemisessa käytetään samaa karsintalogiikkaa. Vaihtoehtoisesti in-order-taulukossa voidaan käyttää funktioita bisect_left/bisect_right — suora BST-läpikäynti käyttää aikaa O(log n + k), kun taas taulukoksi muuntaminen ensin käyttää aina aikaa O(n). Valitkaa suora läpikäynti, ellei useisiin välikyselyihin tarvitse vastata; tällöin alipuiden solmumäärillä täydennetty BST mahdollistaa ajan O(log n) kyselyä kohden.
def count_range(root, low, high):
if not root:
return 0
count = 0
if low <= root.val <= high:
count += 1
if root.val > low:
count += count_range(root.left, low, high)
if root.val < high:
count += count_range(root.right, low, high)
return count
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.right = TreeNode(18)
print(count_range(root, 6, 15)) # 7, 10, 15 = 3BST:n muuntaminen lajitelluksi taulukoksi (koko algoritmi)
BST:n muuntaminen lajitelluksi taulukoksi käyttää aikaa O(n) ja tilaa O(n). Käyttäkää in-order-läpikäyntiä ja lisätkää jokainen arvo taulukkoon. Tämä on lähtökohta monivaiheisille tehtäville, kuten ”merge two BSTs”, ”find the median of a BST” tai ”check if two BSTs have the same in-order sequence”. Tuloksena saatava taulukko tukee indeksin mukaista O(1)-hakua, binäärihakua ja kahden osoittimen tekniikoita, joita BST ei itsessään mahdollista suoraan.
def bst_to_sorted(root):
result = []
def inorder(node):
if not node:
return
inorder(node.left)
result.append(node.val)
inorder(node.right)
inorder(root)
return result
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
root.right.left = TreeNode(6)
root.right.right = TreeNode(9)
print(bst_to_sorted(root)) # [1, 3, 4, 5, 6, 8, 9]
# Binary search on the resulting sorted array:
import bisect
arr = bst_to_sorted(root)
print(bisect.bisect_left(arr, 6)) # 4 (index of 6)Laajennettu BST: alipuiden koot
Laajennettu BST tallentaa jokaiseen solmuun lisätietoja, kuten sen alipuun koon. Alipuiden kokojen avulla k:nneksi pienin alkio voidaan löytää ajassa O(log n): kussakin solmussa, jos vasemman alipuun koko on k-1, nykyinen solmu on vastaus; jos vasemman alipuun koko on vähintään k, jatketaan rekursiivisesti vasemmalle; muussa tapauksessa k:sta vähennetään vasemman alipuun koko ja jatketaan oikealle. Tämä on kilpailuohjelmoinnissa käytettävien järjestystilastopuiden taustalla oleva tietorakenne.
class AugNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
self.size = 1 # subtree size
def get_size(node):
return node.size if node else 0
def update_size(node):
if node:
node.size = 1 + get_size(node.left) + get_size(node.right)
def kth_smallest_aug(root, k):
left_size = get_size(root.left)
if k == left_size + 1:
return root.val # current node is kth
elif k <= left_size:
return kth_smallest_aug(root.left, k)
else:
return kth_smallest_aug(root.right, k - left_size - 1)
print('Augmented BST: O(log n) kth smallest with subtree sizes')Kaikkien kahden solmun väliin jäävien arvojen etsiminen BST:stä
Kun palautetaan kaikki kahden solmun p ja q välissä olevat arvot (joille p.val < q.val), yhdistetään järjestyksessä läpikäynti ja välin perusteella karsiminen: arvoja aletaan kerätä, kun p.val on ohitettu, ja kerääminen lopetetaan q.val-arvon jälkeen. Tämä on välin summan yleistys, ja se antaa kyselyssä määritettyjen arvojen välisen järjestetyn jakson ajassa O(h + k).
def values_between(root, low, high):
result = []
def inorder(node):
if not node:
return
if node.val > low: # might be values > low on left
inorder(node.left)
if low < node.val < high: # strictly between
result.append(node.val)
if node.val < high: # might be values < high on right
inorder(node.right)
inorder(root)
return result
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(7)
root.right.left = TreeNode(12)
root.right.right = TreeNode(18)
print(values_between(root, 6, 15)) # [7, 10, 12]BST:n mediaani
BST:n mediaani on järjestyksessä läpikäynnin keskimmäinen arvo. Kun solmuja on n, mediaani on indeksissä n // 2 (indeksointi alkaa nollasta). Koko järjestetty taulukko voidaan joko kerätä ja käyttää sen indeksiä tai tehdä kaksi läpikäyntiä: ensin lasketaan n solmua, minkä jälkeen tehdään toinen järjestyksessä läpikäynti, joka lopetetaan solmuun n // 2. solmun kohdalla. Vaihtoehtoisesti voidaan etsiä k:s pienin alkio, kun k = n // 2 + 1.
def count_nodes(root):
if not root:
return 0
return 1 + count_nodes(root.left) + count_nodes(root.right)
def median_of_bst(root):
n = count_nodes(root)
if n == 0:
return None
k = n // 2 + 1 # (n+1)/2-th element for odd, n/2+1-th for even
return kth_smallest(root, k)
def kth_smallest(root, k):
count = [0]; result = [None]
def inorder(node):
if not node or result[0] is not None: return
inorder(node.left)
count[0] += 1
if count[0] == k: result[0] = node.val; return
inorder(node.right)
inorder(root); return result[0]
root = TreeNode(5)
root.left = TreeNode(3)
root.right = TreeNode(8)
root.left.left = TreeNode(1)
root.left.right = TreeNode(4)
print(median_of_bst(root)) # 4 (middle of [1,3,4,5,8])Kohdetta lähimpänä olevat K arvoa
Etsitään BST:stä k kohdetta lähimpänä olevaa arvoa. Yksi kahden osoittimen menetelmä on muuntaa BST järjestetyksi taulukoksi ja käyttää k:n kokoista liukuvaa ikkunaa. Vaihtoehtoisesti voidaan käyttää k:n kokoista maksimikekoa, johon etäisyyksiä lisätään ja josta alkioita poistetaan, kun koko ylittää k:n. Järjestettyyn taulukkoon perustuva menetelmä vie aikaa O(n) ja on yksinkertainen; kekomenetelmä vie aikaa O(n log k), mutta toimii suoratoistoympäristössä.
import heapq
def closest_k_values(root, target, k):
# Collect sorted values
arr = []
def inorder(node):
if not node: return
inorder(node.left)
arr.append(node.val)
inorder(node.right)
inorder(root)
# Two-pointer sliding window of size k
left, right = 0, k - 1
while right < len(arr) - 1:
if abs(arr[left] - target) <= abs(arr[right + 1] - target):
break # left is closer, don't advance
left += 1
right += 1
return arr[left:right + 1]
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(closest_k_values(root, 3.7, 2)) # [3, 4]Järjestyksen seuraajaominaisuuden hyödyntäminen
Monet BST-ongelmat palautuvat lajitellussa järjestyksessä seuraavan tai edellisen alkion etsimiseen — BST:n navigoinnilla nämä operaatiot vievät aikaa O(log n). Aiemmin rakennettu iteraattori antaa seuraavan alkion amortisoidussa vakioajassa O(1). Kun yhdistetään k:nneksi pienimmän alkion, välin summan ja lähimmän arvon tuntemus, useimmat BST-haastattelutehtävät voidaan ratkaista kysymällä: ”Miten järjestyksessä läpikäynnin tuottama lajiteltu järjestys yksinkertaistaa tätä?” Tämä metakuvio toimii BST-ongelmanratkaisun kompassina.
# Meta-pattern for BST problems:
# Step 1: What sorted-order property does this exploit?
# Step 2: Is in-order (ascending) or reverse in-order (descending) needed?
# Step 3: Can I prune using BST ordering to avoid O(n) scan?
# Quick reference:
# kth smallest -> in-order, stop at kth node
# kth largest -> reverse in-order, stop at kth node
# range sum -> in-order + BST pruning
# closest value -> walk toward target, track best
# median -> kth with k = n//2+1
# sorted array -> full in-order
# validate -> in-order prev check or min/max bounds
print('Sorted in-order is the universal BST problem tool')Pikatarkistus
Testataan tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheiden ymmärtämistä.
Oppitunnin kertaus
Tässä oppitunnissa opittiin: k:nneksi pienimmän ja suurimman alkion etsiminen järjestyksessä ja käänteisessä järjestyksessä tapahtuvalla läpikäynnillä ajassa O(h+k), välin summan laskeminen BST:n karsinnan avulla tehokkaita välikyselyitä varten sekä BST:n muuntaminen järjestetyksi taulukoksi taulukkopohjaisten algoritmien perustaksi. Seuraavaksi tutustutaan kekorakenteisiin ja prioriteettijonoihin.
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
Usein kysytyt kysymykset
Onko oppitunti ”K:nneksi pienin, alueen summa ja BST järjestetyksi taulukoksi” ilmainen?
Kyllä – oppitunnin ”K:nneksi pienin, alueen summa ja BST järjestetyksi taulukoksi” 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 ”K:nneksi pienin, alueen summa ja BST järjestetyksi taulukoksi”?
Hyödyntäkää järjestettyä in-order-läpikäyntiä löytääksenne k:nneksi pienimmän alkion ajassa O(k) ja laskeaksenne alueelle sijoittuvien arvojen summan ajassa O(log n + k). 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 ”K:nneksi pienin, alueen summa ja BST järjestetyksi taulukoksi”-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
- BST:n lisäys ja haku
- BST:n poisto: kolme tapausta
- BST:n kelvollisuuden ja in-order-ominaisuuksien tarkistaminen
- K:nneksi pienin, alueen summa ja BST järjestetyksi taulukoksi