In-order-, pre-order- ja post-order-DFS
Toteuttakaa kaikki kolme DFS-läpikäyntiä rekursiivisesti ja iteroivasti eksplisiittisen pinon avulla sekä selittäkää, milloin kukin järjestys on hyödyllinen.
In-order-, pre-order- ja post-order-DFS on ilmainen DSA Interview Prep-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea tästä oppimispolusta kokonaan mitkä tahansa 3 oppituntia ilmaiseksi — sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä käytännön harjoittelun sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Oppitunti kuuluu DSA Interview Prep-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.
Kolme DFS-läpikäyntijärjestystä
DFS-läpikäynti binääripuussa käsittelee solmut yhdessä kolmesta järjestyksestä sen mukaan, milloin juuri käsitellään suhteessa sen lapsiin. Esijärjestys: juuri → vasen → oikea. Sisäjärjestys: vasen → juuri → oikea. Jälkijärjestys: vasen → oikea → juuri. Nimet kertovat, mihin juuri sijoittuu järjestyksessä. Kaikkien kolmen ymmärtäminen on olennaista, koska eri ongelmat edellyttävät eri järjestyksiä.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# Build: 1 -> left=2(left=4,right=5), right=3
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
# pre: 1 2 4 5 3
# in: 4 2 5 1 3
# post: 4 5 2 3 1
print('Tree built successfully')Rekursiivinen esijärjestysläpikäynti
Esijärjestyksessä nykyinen solmu käsitellään ennen sen alipuita. Tämä vastaa puun luonnollista ylhäältä alas lukemista, ja sitä käytetään puun kopiointiin, serialisointiin ja etuliikemuotoisen lausekkeen arviointiin. Rekursiivinen toteutus on erittäin lyhyt, mutta se rakentaa kutsupinon, jonka syvyys on O(h), jossa h on puun korkeus.
def preorder(root):
if not root:
return []
return [root.val] + preorder(root.left) + preorder(root.right)
# More memory-efficient with an accumulator:
def preorder_v2(root, result=None):
if result is None:
result = []
if not root:
return result
result.append(root.val) # PROCESS ROOT FIRST
preorder_v2(root.left, result)
preorder_v2(root.right, result)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_v2(root)) # [1, 2, 4, 5, 3]Rekursiivinen sisäjärjestysläpikäynti
Sisäjärjestysläpikäynnissä käydään ensin läpi vasen alipuu, sitten juuri ja lopuksi oikea alipuu. Binäärihakupuussa sisäjärjestysläpikäynti tuottaa aina lajitellun jonon — tätä ominaisuutta hyödynnetään esimerkiksi BST:n kelvollisuuden tarkistamisessa, k:nnen pienimmän alkion etsimisessä ja BST:n muuntamisessa lajitelluksi taulukoksi. Se on tärkein läpikäyntijärjestys, joka BST-tehtävissä on tunnettava.
def inorder(root, result=None):
if result is None:
result = []
if not root:
return result
inorder(root.left, result) # left subtree first
result.append(root.val) # PROCESS ROOT MIDDLE
inorder(root.right, result) # right subtree last
return result
# For a BST, inorder gives sorted output:
from collections import deque
def make_bst():
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
return root
bst = make_bst()
print(inorder(bst)) # [1, 2, 3, 4, 6] - sorted!Rekursiivinen jälkijärjestysläpikäynti
Jälkijärjestysläpikäynnissä molemmat lapset käsitellään ennen nykyistä solmua. Tämä alhaalta ylöspäin etenevä järjestys on luonteva, kun vanhemman laskenta riippuu sen lasten tuloksista — esimerkiksi alipuiden kokojen laskennassa, puun poistamisessa tai lausekepuun arvioinnissa. Useimmat puutehtävät, joissa tietoa välitetään ylöspäin, käyttävät implisiittistä jälkijärjestyslogiikkaa.
def postorder(root, result=None):
if result is None:
result = []
if not root:
return result
postorder(root.left, result) # left subtree
postorder(root.right, result) # right subtree
result.append(root.val) # PROCESS ROOT LAST
return result
# Use case: delete a tree (children before parent)
def delete_tree(root):
if not root:
return
delete_tree(root.left)
delete_tree(root.right)
print(f'Deleting node {root.val}') # safe: children gone
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(postorder(root)) # [4, 2, 3, 1]Iteratiivinen esijärjestys eksplisiittisen pinon avulla
Rekursiosyvyyden rajoitusten välttämiseksi toteuttakaa DFS iteratiivisesti käyttämällä eksplisiittistä pinoa. Esijärjestystä varten työntäkää juuri pinoon ja poistakaa kullakin iteraatiolla solmu pinosta, tallentakaa se ja työntäkää sen oikea lapsi ja sitten vasen lapsi (oikea ensin, jotta vasen käsitellään ensin). Tämä jäljittelee kutsupinon LIFO-käyttäytymistä ja on ensisijainen menetelmä syville puille, joissa Pythonin oletusarvoinen 1000:n rekursioraja ylittyisi.
def preorder_iterative(root):
if not root:
return []
result = []
stack = [root]
while stack:
node = stack.pop()
result.append(node.val) # process now
if node.right: # push right FIRST
stack.append(node.right)
if node.left: # push left second (popped first)
stack.append(node.left)
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(preorder_iterative(root)) # [1, 2, 4, 5, 3]Iteratiivinen sisäjärjestys pinon avulla
Iteratiivinen sisäjärjestys on hieman hankalampi. Käyttäkää pinoa ja osoitinta curr: siirtykää vasemmalle niin pitkälle kuin mahdollista ja työntäkää jokainen solmu pinoon. Kun ette voi enää siirtyä vasemmalle, poistakaa solmu pinosta, tallentakaa se ja siirtykää oikealle. Tämä kaava — työnnä vasemmalle, kunnes vastaan tulee null, poista ja käsittele, siirry sitten oikealle — on olennainen iteratiivinen tekniikka, jota käytetään esimerkiksi BST-iteraattoritehtävissä.
def inorder_iterative(root):
result = []
stack = []
curr = root
while curr or stack:
# Go as far left as possible
while curr:
stack.append(curr)
curr = curr.left
# Pop and process
curr = stack.pop()
result.append(curr.val)
# Move to right subtree
curr = curr.right
return result
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(inorder_iterative(root)) # [4, 2, 5, 1, 3]Iteratiivinen jälkijärjestys kahden pinon avulla
Iteratiiviseen jälkijärjestykseen liittyy näppärä temppu: suorittakaa muokattu esijärjestys (juuri → oikea → vasen) ja kerätkää tulokset käänteisessä järjestyksessä. Työntäkää juuri pinoon, poistakaa solmu ja lisätkää se tuloksen alkuun, minkä jälkeen työntäkää vasen ja sitten oikea. Kääntäminen muuttaa juuri-oikea-vasen-järjestyksen vasen-oikea-juuri-järjestykseksi — mikä on täsmälleen jälkijärjestys. Vaihtoehtoisesti voitte käyttää prev-osoitinta viimeksi käsitellyn solmun seuraamiseen yhden pinon avulla.
from collections import deque
def postorder_iterative(root):
if not root:
return []
result = deque()
stack = [root]
while stack:
node = stack.pop()
result.appendleft(node.val) # prepend = reverse pre-order
if node.left:
stack.append(node.left) # push left first
if node.right:
stack.append(node.right) # push right second
return list(result)
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
print(postorder_iterative(root)) # [4, 5, 2, 3, 1]Milloin mitäkin läpikäyntijärjestystä käytetään
Oikean läpikäyntijärjestyksen valinta on haastattelussa tärkeä vihje osaamisestanne. Käyttäkää esijärjestystä, kun vanhempi on käsiteltävä ennen lapsiaan (puun serialisointi, rakenteen kopiointi). Käyttäkää sisäjärjestystä BST-puissa lajitellun järjestyksen hyödyntämiseen. Käyttäkää jälkijärjestystä, kun laskettavat arvot riippuvat molemmista lapsista (korkeus, halkaisija, alipuun summa). BFS on suositeltava lyhimmän polun ja solmujen tasoittaisen ryhmittelyn tehtävissä.
# Pattern summary:
# Pre-order -> top-down: parent info flows DOWN to children
# In-order -> BST sorted property, kth element, validate BST
# Post-order -> bottom-up: children info flows UP to parent
# BFS -> shortest path, level grouping, level averages
# Example: compute subtree sum (post-order because
# we need left + right sum before computing total)
def subtree_sum(root):
if not root:
return 0
left = subtree_sum(root.left)
right = subtree_sum(root.right)
return root.val + left + right # uses children FIRST
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
print(subtree_sum(root)) # 6Morrisin läpikäynti: sisäjärjestys tilavaativuudella O(1)
Morrisin läpikäynti saavuttaa sisäjärjestyksessä tilavaativuuden O(1) muokkaamalla puuta väliaikaisesti. Etsikää jokaiselle vasemman alipuun sisältävälle solmulle sisäjärjestyksen edeltäjä eli vasemman alipuun oikeanpuoleisin solmu ja yhdistäkää sen oikea osoitin takaisin nykyiseen solmuun. Vierailun jälkeen palauttakaa yhteys ennalleen. Tätä edistynyttä tekniikkaa kysytään huipputason haastatteluissa, kun haastattelija kysyy: onnistuisiko tämä O(1):n lisätilalla?
def morris_inorder(root):
result = []
curr = root
while curr:
if not curr.left:
result.append(curr.val)
curr = curr.right
else:
# Find in-order predecessor
pred = curr.left
while pred.right and pred.right != curr:
pred = pred.right
if not pred.right:
# Make thread and move left
pred.right = curr
curr = curr.left
else:
# Remove thread, visit, move right
pred.right = None
result.append(curr.val)
curr = curr.right
return result
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(morris_inorder(root)) # [1, 2, 3, 4, 6]Puun rekonstruointi läpikäyntijärjestyksistä
Esijärjestys- ja sisäjärjestystaulukkojen perusteella voitte rekonstruoida alkuperäisen puun. Esijärjestyksen ensimmäinen alkio on aina juuri. Etsikää juuri sisäjärjestystaulukosta — kaikki sen vasemmalla puolella oleva kuuluu vasempaan alipuuhun ja kaikki oikealla puolella oleva oikeaan alipuuhun. Soveltakaa tätä rekursiivisesti alitaulukoihin. Aikavaativuus on O(n), kun indeksit haetaan hajautustaulun avulla.
def build_from_preorder_inorder(preorder, inorder):
if not preorder:
return None
root_val = preorder[0]
root = TreeNode(root_val)
mid = inorder.index(root_val)
# left subtree: inorder[0:mid], preorder[1:mid+1]
root.left = build_from_preorder_inorder(
preorder[1:mid+1], inorder[:mid])
# right subtree: inorder[mid+1:], preorder[mid+1:]
root.right = build_from_preorder_inorder(
preorder[mid+1:], inorder[mid+1:])
return root
pre = [3, 9, 20, 15, 7]
ino = [9, 3, 15, 20, 7]
root = build_from_preorder_inorder(pre, ino)
print(root.val, root.left.val, root.right.val) # 3 9 20Läpikäyntien aika- ja tilavaativuudet
Kaikkien kolmen DFS-läpikäynnin aikavaativuus on O(n), koska jokainen solmu käsitellään täsmälleen kerran. Tilavaativuus on O(h), jossa h on puun korkeus — tasapainoisissa puissa O(log n) ja vinoissa puissa O(n) (kutsupinon tai eksplisiittisen pinon vuoksi). Iteratiiviset toteutukset välttävät Pythonin rekursiorajan, mutta niiden asymptoottinen tilavaativuus on sama. Morris saavuttaa ainoana tilavaativuuden O(1) käyttämällä puun oikeanpuoleisia osoittimia uudelleen.
# Complexity table:
# Traversal | Time | Space (recursion) | Space (iterative)
# -----------|------|-------------------|------------------
# Pre-order | O(n) | O(h) | O(h)
# In-order | O(n) | O(h) | O(h)
# Post-order | O(n) | O(h) | O(h)
# Morris | O(n) | O(1) | O(1)
# BFS | O(n) | O(w) | O(w)
# h = height, w = max width
# Balanced: h = log n, w = n/2
# Skewed: h = n, w = 1
print('O(n) time for all traversals')Pikatarkistus
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteiden ymmärryksenne.
Oppitunnin kertaus
Tässä oppitunnissa opitte: kolme DFS-läpikäyntijärjestystä (pre, in, post) ja milloin kutakin käytetään, rekursiiviset ja iteratiiviset toteutukset eksplisiittisen pinon avulla sekä Morrisin O(1)-tilatekniikan. Seuraavaksi tarkastelemme binääripuiden halkaisijan, korkeuden ja tasapainon laskemista.
Opi Python 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
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”In-order-, pre-order- ja post-order-DFS” ilmainen?
Kyllä — voit lukea täällä verkossa kokonaan ilmaiseksi mitkä tahansa DSA Interview Prep-oppimispolun 3 oppituntia, myös oppitunnin “In-order-, pre-order- ja post-order-DFS”. Sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä interaktiiviset harjoitukset sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”In-order-, pre-order- ja post-order-DFS”?
Toteuttakaa kaikki kolme DFS-läpikäyntiä rekursiivisesti ja iteroivasti eksplisiittisen pinon avulla sekä selittäkää, milloin kukin järjestys on hyödyllinen. Harjoittelet DSA Interview Prep-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni DSA Interview Prep-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin DSA Interview Prep-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”In-order-, pre-order- ja post-order-DFS”-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ä DSA Interview Prep-oppitunnilla?
Kyllä. Jokainen DSA Interview Prep-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