In-Order-, Pre-Order- und Post-Order-DFS
Implementieren Sie alle drei DFS-Traversierungen rekursiv und iterativ mit einem expliziten Stapel und erklären Sie, wann jede Reihenfolge nützlich ist.
In-Order-, Pre-Order- und Post-Order-DFS ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Drei DFS-Durchlaufreihenfolgen
DFS in einem Binärbaum besucht Knoten in einer von drei Reihenfolgen, abhängig davon, wann die Wurzel im Verhältnis zu ihren Kindknoten verarbeitet wird. Preorder: Wurzel → links → rechts. Inorder: links → Wurzel → rechts. Postorder: links → rechts → Wurzel. Die Bezeichnungen zeigen, wo die Wurzel in der Reihenfolge steht. Das Verständnis aller drei Reihenfolgen ist unverzichtbar, da unterschiedliche Aufgaben unterschiedliche Reihenfolgen erfordern.
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')Rekursiver Preorder-Durchlauf
Beim Preorder-Durchlauf wird der aktuelle Knoten vor seinen Teilbäumen verarbeitet. Dies entspricht der natürlichen Lektüre eines Baums von oben nach unten und wird zum Kopieren von Bäumen, zur Serialisierung und zur Auswertung von Präfixausdrücken verwendet. Die rekursive Implementierung ist sehr kurz, baut jedoch einen Aufrufstapel mit der Tiefe O(h) auf, wobei h der Höhe des Baums entspricht.
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]Rekursiver Inorder-Durchlauf
Der Inorder-Durchlauf besucht zuerst den linken Teilbaum, dann die Wurzel und anschließend den rechten Teilbaum. Bei einem Binärsuchbaum erzeugt der Inorder-Durchlauf immer eine sortierte Sequenz – diese Eigenschaft wird bei Aufgaben wie der Validierung eines BST, dem k-kleinsten Element und der Umwandlung eines BST in ein sortiertes Array verwendet. Für Aufgaben zu BSTs ist dies der wichtigste Durchlauf, den Sie kennen sollten.
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!Rekursiver Postorder-Durchlauf
Beim Postorder-Durchlauf werden beide Kindknoten vor dem aktuellen Knoten verarbeitet. Diese Reihenfolge von unten nach oben ist natürlich, wenn die Berechnung des Elternknotens von den Ergebnissen seiner Kindknoten abhängt – beispielsweise beim Berechnen von Teilbaumgrößen, beim Löschen eines Baums oder beim Auswerten eines Ausdrucksbaums. Die meisten Baumaufgaben, bei denen Informationen nach oben weitergegeben werden, verwenden implizit eine Postorder-Logik.
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]Iterativer Preorder-Durchlauf mit einem Stapel
Um Beschränkungen der Rekursionstiefe zu vermeiden, implementieren Sie DFS iterativ mit einem expliziten Stapel. Für Preorder legen Sie die Wurzel auf den Stapel und entfernen in jeder Iteration einen Knoten, speichern ihn und legen anschließend zuerst den rechten und dann den linken Kindknoten auf den Stapel (rechts zuerst, damit links zuerst verarbeitet wird). Dies bildet das LIFO-Verhalten des Aufrufstapels nach und ist der bevorzugte Ansatz für tiefe Bäume, bei denen Pythons standardmäßige Rekursionsgrenze von 1000 überschritten würde.
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]Iterativer Inorder-Durchlauf mit einem Stapel
Der iterative Inorder-Durchlauf ist etwas anspruchsvoller. Verwenden Sie einen Stapel und einen Zeiger curr: Gehen Sie so weit wie möglich nach links und legen Sie jeden Knoten auf den Stapel. Wenn Sie nicht weiter nach links gehen können, entfernen Sie einen Knoten vom Stapel, speichern Sie ihn und gehen Sie anschließend nach rechts. Dieses Muster – bis zum Nullwert nach links gehen, einen Knoten entfernen und verarbeiten, dann nach rechts gehen – ist eine grundlegende iterative Technik, die bei Aufgaben zu BST-Iteratoren häufig vorkommt.
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]Iterativer Postorder-Durchlauf mit zwei Stapeln
Für den iterativen Postorder-Durchlauf gibt es einen eleganten Trick: Führen Sie einen modifizierten Preorder-Durchlauf (Wurzel → rechts → links) aus und sammeln Sie die Ergebnisse in umgekehrter Reihenfolge. Legen Sie die Wurzel auf den Stapel, entfernen Sie einen Knoten und fügen Sie ihn am Anfang des Ergebnisses ein; legen Sie anschließend zuerst den linken und dann den rechten Kindknoten auf den Stapel. Durch die Umkehrung wird aus Wurzel-rechts-links die Reihenfolge links-rechts-Wurzel – genau der Postorder-Durchlauf. Alternativ können Sie mit einem prev-Zeiger den zuletzt besuchten Knoten verfolgen und nur einen Stapel verwenden.
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]Den richtigen Durchlauf auswählen
Die Wahl des richtigen Durchlaufs ist ein wichtiges Signal im Vorstellungsgespräch. Verwenden Sie Preorder, wenn Sie einen Elternknoten vor seinen Kindknoten verarbeiten müssen (Baum serialisieren, Struktur kopieren). Verwenden Sie Inorder bei BSTs, um die sortierte Reihenfolge zu nutzen. Verwenden Sie Postorder, wenn Sie Werte berechnen, die von beiden Kindknoten abhängen (Höhe, Durchmesser, Teilbaumsumme). BFS eignet sich besonders für Aufgaben zu kürzesten Pfaden und zur Gruppierung nach Ebenen.
# 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-Durchlauf: Inorder mit O(1)-Speicher
Der Morris-Durchlauf erreicht einen Inorder-Durchlauf mit O(1) Speicher, indem der Baum vorübergehend verändert wird. Suchen Sie für jeden Knoten mit einem linken Teilbaum den Inorder-Vorgänger (den Knoten ganz rechts im linken Teilbaum) und verknüpfen Sie dessen rechten Zeiger zurück mit dem aktuellen Knoten. Stellen Sie die Verknüpfung nach dem Besuch wieder her. Diese fortgeschrittene Technik wird in anspruchsvollen Vorstellungsgesprächen gefragt, wenn der Interviewer fragt: „Können Sie das mit O(1) zusätzlichem Speicher lösen?“
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]Baum aus Durchläufen rekonstruieren
Wenn Preorder- und Inorder-Arrays gegeben sind, können Sie den ursprünglichen Baum rekonstruieren. Das erste Element von Preorder ist immer die Wurzel. Suchen Sie diese Wurzel im Inorder-Array – alles links davon gehört zum linken Teilbaum, alles rechts davon zum rechten Teilbaum. Wenden Sie dieses Verfahren rekursiv auf die Teilarrays an. Mit einer Hashmap für die Indexsuche beträgt die Zeitkomplexität O(n).
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 20Zusammenfassung von Laufzeit und Speicher der Durchläufe
Alle drei DFS-Durchläufe haben eine Zeitkomplexität von O(n), da jeder Knoten genau einmal besucht wird. Die Speicherkomplexität beträgt O(h), wobei h die Höhe des Baums ist – O(log n) bei ausgeglichenen Bäumen und O(n) bei schiefen Bäumen (aufgrund des Aufrufstapels oder des expliziten Stapels). Iterative Implementierungen vermeiden Pythons Rekursionsgrenze, verwenden aber asymptotisch ebenso viel Speicher. Der Morris-Durchlauf erreicht als einzige Variante O(1) Speicher, indem er die rechten Zeiger des Baums wiederverwendet.
# 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')Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie Folgendes gelernt: die drei DFS-Durchlaufreihenfolgen (Preorder, Inorder, Postorder) und wann welche zu wählen ist, rekursive und iterative Implementierungen mit einem expliziten Stapel sowie die Morris-Technik mit O(1) Speicher. Als Nächstes untersuchen wir das Berechnen von Durchmesser, Höhe und Balance von Binärbäumen.
Häufig gestellte Fragen
Ist die Lektion „In-Order-, Pre-Order- und Post-Order-DFS“ kostenlos?
Ja — der vollständige Text von „In-Order-, Pre-Order- und Post-Order-DFS“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „In-Order-, Pre-Order- und Post-Order-DFS“?
Implementieren Sie alle drei DFS-Traversierungen rekursiv und iterativ mit einem expliziten Stapel und erklären Sie, wann jede Reihenfolge nützlich ist. Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „In-Order-, Pre-Order- und Post-Order-DFS“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- TreeNode-Klasse und BFS nach Ebenen
- In-Order-, Pre-Order- und Post-Order-DFS
- Durchmesser, Höhe und balancierte Bäume
- Pfadsumme und niedrigster gemeinsamer Vorfahr