In-order, pre-order och post-order DFS
Implementera alla tre DFS-genomgångarna rekursivt och iterativt med en explicit stack och förklara när varje ordning är användbar.
In-order, pre-order och post-order DFS är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 2 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Tre DFS-traverseringsordningar
DFS på ett binärt träd besöker noderna i en av tre ordningar, beroende på när roten bearbetas i förhållande till dess barn. Preorder: rot → vänster → höger. Inorder: vänster → rot → höger. Postorder: vänster → höger → rot. Namnen visar var roten placeras i sekvensen. Det är viktigt att förstå alla tre, eftersom olika problem kräver olika ordningar.
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')Rekursiv preorder-traversering
I preorder bearbetas den aktuella noden före dess delträd. Detta motsvarar den naturliga läsningen av ett träd uppifrån och ned och används för att kopiera träd, serialisera dem och utvärdera prefixuttryck. Den rekursiva implementationen är mycket kort, men bygger en anropsstack med djupet O(h), där h är trädets höjd.
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]Rekursiv inorder-traversering
Inorder-traversering besöker det vänstra delträdet, sedan roten och därefter det högra delträdet. För ett binärt sökträd ger inorder-traversering alltid en sorterad sekvens — denna egenskap används i problem som validering av BST, det k:te minsta elementet och konvertering från BST till en sorterad array. Det är den viktigaste traverseringen att känna till för BST-problem.
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!Rekursiv postorder-traversering
Postorder-traversering bearbetar båda barnen före den aktuella noden. Denna ordning nerifrån och upp är naturlig när förälderns beräkning beror på barnens resultat — till exempel vid beräkning av delträdens storlek, borttagning av ett träd eller utvärdering av ett uttrycksträd. De flesta trädproblem som skickar information uppåt använder implicit postorderlogik.
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]Iterativ preorder med en stack
För att undvika begränsningar i rekursionsdjupet kan ni implementera DFS iterativt med en explicit stack. För preorder: lägg roten på stacken och ta sedan i varje iteration bort en nod, registrera den och lägg först dess högra barn och sedan dess vänstra barn på stacken (höger först, så att vänster behandlas först). Detta efterliknar anropsstackens LIFO-beteende och är standardmetoden för djupa träd där Pythons standardgräns för rekursion på 1000 skulle överskridas.
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]Iterativ inorder med en stack
Iterativ inorder är något mer komplicerad. Använd en stack och en pekare curr: gå så långt åt vänster som möjligt och lägg varje nod på stacken. När ni inte kan gå längre åt vänster tar ni bort en nod, registrerar den och går sedan åt höger. Detta mönster — lägg åt vänster tills null, ta bort och bearbeta, gå sedan åt höger — är en central iterativ teknik som förekommer i problem med BST-iteratorer.
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]Iterativ postorder med två stackar
Iterativ postorder har ett smart trick: kör en modifierad preorder (rot → höger → vänster) och samla resultaten i omvänd ordning. Lägg roten på stacken, ta bort den och lägg den först i resultatet, och lägg sedan vänster barn följt av höger barn på stacken. Omvändningen omvandlar rot-höger-vänster till vänster-höger-rot — vilket är exakt postorder. Alternativt kan ni använda en prev-pekare för att hålla reda på den senast besökta noden med en enda stack.
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]När ska ni välja vilken traversering
Att välja rätt traversering är en viktig signal i en intervju. Använd preorder när ni behöver bearbeta en förälder före dess barn (serialisera ett träd, kopiera en struktur). Använd inorder för BST-träd för att dra nytta av sorteringsordningen. Använd postorder när ni beräknar värden som beror på båda barnen (höjd, diameter, delträdssumma). BFS föredras för problem med kortaste vägen och gruppering per nivå.
# 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)) # 6Morris-traversering: O(1) minne för inorder
Morris-traversering uppnår O(1) minne för inorder genom att tillfälligt ändra trädet. För varje nod med ett vänsterdelträd hittar ni inorder-föregångaren (den högra noden längst ut i vänsterdelträdet) och länkar dess högra pekare tillbaka till den aktuella noden. Efter besöket återställer ni länken. Detta är en avancerad teknik som efterfrågas i intervjuer på högsta nivå när intervjuaren frågar: 'kan du göra det med O(1) extra minne?'
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]Återskapa ett träd från traverseringar
Med givna preorder- och inorder-arrayer kan ni återskapa det ursprungliga trädet. Det första elementet i preorder är alltid roten. Leta upp roten i inorder-arrayen — allt till vänster om den hör till vänster delträd och allt till höger hör till höger delträd. Tillämpa detta rekursivt på delarrayerna. Tidskomplexiteten är O(n) med en indexuppslagning i en hash map.
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 20Sammanfattning av traverseringarnas tids- och minneskomplexitet
Alla tre DFS-traverseringar har tidskomplexiteten O(n), eftersom varje nod besöks exakt en gång. Minneskomplexiteten är O(h), där h är trädets höjd — O(log n) för balanserade träd och O(n) för snedfördelade träd (på grund av anropsstacken eller den explicita stacken). Iterativa implementationer undviker Pythons rekursionsgräns, men använder samma asymptotiska minne. Morris-traversering uppnår unikt O(1) minne genom att återanvända trädets högra pekare.
# 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')Snabbkontroll
Testa er förståelse av begreppen Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Lektionssammanfattning
I den här lektionen har ni lärt er: tre DFS-traverseringsordningar (preorder, inorder och postorder) och när ni ska välja respektive ordning, rekursiva och iterativa implementationer med en explicit stack samt Morris-tekniken med O(1) minne. Härnäst utforskar vi hur man beräknar diameter, höjd och balans i binära träd.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”In-order, pre-order och post-order DFS” gratis?
Ja – hela texten till ”In-order, pre-order och post-order DFS” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”In-order, pre-order och post-order DFS”?
Implementera alla tre DFS-genomgångarna rekursivt och iterativt med en explicit stack och förklara när varje ordning är användbar. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 2 av 4.
Hur lång tid tar lektionen ”In-order, pre-order och post-order DFS”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- TreeNode-klassen och BFS nivå för nivå
- In-order, pre-order och post-order DFS
- Diameter, höjd och balanserade träd
- Summor av vägar och närmaste gemensamma förfader