DFS w kolejności inorder, preorder i postorder
Zaimplementują Państwo wszystkie trzy przejścia DFS rekurencyjnie i iteracyjnie z jawnym stosem, wyjaśniając, kiedy przydatna jest każda kolejność.
DFS w kolejności inorder, preorder i postorder to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Trzy porządki przechodzenia DFS
DFS drzewa binarnego odwiedza węzły w jednym z trzech porządków, zależnie od tego, kiedy korzeń jest przetwarzany względem swoich dzieci. Pre-order: korzeń → lewe poddrzewo → prawe poddrzewo. In-order: lewe poddrzewo → korzeń → prawe poddrzewo. Post-order: lewe poddrzewo → prawe poddrzewo → korzeń. Nazwy wskazują, gdzie w sekwencji znajduje się korzeń. Zrozumienie wszystkich trzech porządków jest niezbędne, ponieważ różne zadania wymagają różnych sposobów przechodzenia.
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')Rekurencyjne przejście pre-order
W przejściu pre-order bieżący węzeł jest przetwarzany przed jego poddrzewami. Odzwierciedla to naturalne odczytywanie drzewa z góry na dół i znajduje zastosowanie przy kopiowaniu drzewa, serializacji oraz obliczaniu wartości wyrażeń prefiksowych. Implementacja rekurencyjna jest bardzo krótka, ale tworzy stos wywołań o głębokości O(h), gdzie h oznacza wysokość drzewa.
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]Rekurencyjne przejście in-order
Przejście in-order odwiedza lewe poddrzewo, następnie korzeń, a potem prawe poddrzewo. W przypadku drzewa BST przejście in-order zawsze tworzy posortowaną sekwencję — właściwość tę wykorzystują zadania takie jak sprawdzanie poprawności BST, znajdowanie k-tego najmniejszego elementu oraz zamiana BST na posortowaną tablicę. Jest to najważniejszy porządek przechodzenia, który należy znać w zadaniach dotyczących BST.
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!Rekurencyjne przejście post-order
Przejście post-order przetwarza oba dzieci przed bieżącym węzłem. Ten porządek oddolny jest naturalny, gdy obliczenia dla rodzica zależą od wyników uzyskanych dla jego dzieci — na przykład przy obliczaniu rozmiarów poddrzew, usuwaniu drzewa lub obliczaniu wartości drzewa wyrażeń. Większość zadań dotyczących drzew, w których informacje są przekazywane w górę, korzysta z niejawnej logiki post-order.
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]Iteracyjne przejście pre-order ze stosem
Aby uniknąć ograniczeń głębokości rekurencji, DFS należy zaimplementować iteracyjnie, używając jawnego stosu. W przypadku pre-order należy umieścić korzeń na stosie, a następnie w każdej iteracji zdjąć węzeł ze stosu, zapisać go i umieścić na stosie najpierw jego prawe dziecko, a potem lewe (prawe najpierw, aby lewe zostało przetworzone jako pierwsze). Odwzorowuje to zachowanie stosu wywołań w modelu LIFO i jest standardowym rozwiązaniem dla głębokich drzew, w których domyślny limit rekurencji Pythona wynoszący 1000 byłby niewystarczający.
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]Iteracyjne przejście in-order ze stosem
Iteracyjne przejście in-order jest nieco trudniejsze. Należy użyć stosu i wskaźnika curr: przechodzić maksymalnie w lewo, umieszczając na stosie każdy napotkany węzeł. Gdy nie można już przejść dalej w lewo, należy zdjąć węzeł ze stosu, zapisać go, a następnie przejść w prawo. Ten schemat — umieszczaj węzły na stosie, idąc w lewo aż do wartości null, zdejmij i przetwórz węzeł, a następnie przejdź w prawo — to podstawowa technika iteracyjna pojawiająca się w zadaniach dotyczących iteratora BST.
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]Iteracyjne przejście post-order z dwoma stosami
Iteracyjne przejście post-order wykorzystuje sprytną sztuczkę: wykonuje zmodyfikowane przejście pre-order (korzeń → prawe poddrzewo → lewe poddrzewo), a następnie zbiera wyniki w odwrotnej kolejności. Należy umieścić korzeń na stosie, zdejmować węzły i dodawać je na początku wyniku, a następnie umieszczać na stosie najpierw lewe dziecko, a potem prawe. Odwrócenie kolejności zamienia korzeń-prawe-lewe na lewe-prawe-korzeń — dokładnie tak wygląda post-order. Alternatywnie można użyć wskaźnika prev do śledzenia ostatnio odwiedzonego węzła przy użyciu jednego stosu.
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]Kiedy wybrać poszczególne przejście
Wybór właściwego sposobu przechodzenia jest ważnym sygnałem podczas rozmowy rekrutacyjnej. Należy użyć pre-order, gdy trzeba przetworzyć rodzica przed jego dziećmi (serializacja drzewa, kopiowanie struktury). In-order stosuje się w przypadku BST, aby wykorzystać uporządkowanie rosnące. Post-order należy wybrać przy obliczaniu wartości zależnych od obojga dzieci (wysokość, średnica, suma poddrzewa). BFS jest preferowany w zadaniach dotyczących najkrótszej ścieżki i grupowania węzłów według poziomów.
# 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)) # 6Przejście Morrisa: in-order z pamięcią O(1)
Przejście Morrisa osiąga złożoność pamięciową O(1) dla przejścia in-order dzięki tymczasowej modyfikacji drzewa. Dla każdego węzła mającego lewe poddrzewo należy znaleźć poprzednika w porządku in-order (najbardziej prawy węzeł lewego poddrzewa) i połączyć jego prawy wskaźnik z bieżącym węzłem. Po odwiedzeniu węzła należy przywrócić to połączenie. Jest to zaawansowana technika pojawiająca się podczas rozmów rekrutacyjnych na najwyższe stanowiska, gdy rekruter pyta: „czy można rozwiązać to zadanie przy użyciu O(1) dodatkowej pamięci?”
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]Odtwarzanie drzewa na podstawie przejść
Mając tablice pre-order i in-order, można odtworzyć oryginalne drzewo. Pierwszy element tablicy pre-order jest zawsze korzeniem. Należy znaleźć ten korzeń w tablicy in-order — wszystkie elementy po jego lewej stronie należą do lewego poddrzewa, a wszystkie po prawej do prawego poddrzewa. Następnie trzeba rekurencyjnie zastosować tę samą zasadę do podtablic. Złożoność czasowa wynosi O(n), jeśli do wyszukiwania indeksu użyje się mapy haszującej.
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 20Podsumowanie złożoności czasowej i pamięciowej przejść
Wszystkie trzy przejścia DFS mają złożoność czasową O(n), ponieważ każdy węzeł jest odwiedzany dokładnie raz. Złożoność pamięciowa wynosi O(h), gdzie h oznacza wysokość drzewa — O(log n) dla drzew zrównoważonych i O(n) dla drzew silnie niezrównoważonych (ze względu na stos wywołań lub stos jawny). Implementacje iteracyjne omijają limit rekurencji Pythona, ale mają taką samą złożoność asymptotyczną pod względem pamięci. Przejście Morrisa jako jedyne osiąga złożoność pamięciową O(1), ponownie wykorzystując prawe wskaźniki drzewa.
# 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')Szybki test
Sprawdź swoją znajomość zagadnień Data Structures & Algorithms — Coding Interview Prep z tego rozdziału.
Podsumowanie lekcji
W tej lekcji poznano: trzy porządki przechodzenia DFS (pre, in, post) oraz zasady wyboru każdego z nich, implementacje rekurencyjne i iteracyjne z użyciem jawnego stosu, a także technikę Morrisa z pamięcią O(1). Następnie omówione zostanie obliczanie średnicy, wysokości i równowagi drzew binarnych.
Często zadawane pytania
Czy lekcja „DFS w kolejności inorder, preorder i postorder” jest bezpłatna?
Tak — pełny tekst „DFS w kolejności inorder, preorder i postorder” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „DFS w kolejności inorder, preorder i postorder”?
Zaimplementują Państwo wszystkie trzy przejścia DFS rekurencyjnie i iteracyjnie z jawnym stosem, wyjaśniając, kiedy przydatna jest każda kolejność. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „DFS w kolejności inorder, preorder i postorder”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Klasa TreeNode i BFS poziomami
- DFS w kolejności inorder, preorder i postorder
- Średnica, wysokość i drzewa zrównoważone
- Suma ścieżki i najniższy wspólny przodek