in-order、pre-order、post-order DFS
3種類すべてのDFS走査を、再帰と明示的なスタックを使う反復処理で実装し、それぞれの順序が役立つ場面を説明します。
「in-order、pre-order、post-order DFS」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
3種類のDFS走査順序
二分木のDFSでは、子ノードに対して根を処理するタイミングによって、3種類の順序のいずれかでノードを訪問します。先行順：根 → 左 → 右。中間順：左 → 根 → 右。後行順：左 → 右 → 根。名前を見ると、列の中で根がどこに入るかが分かります。問題によって必要な順序が異なるため、3種類すべてを理解することが重要です。
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')再帰による先行順走査
先行順では、現在のノードを部分木よりも先に処理します。これは木を上から下へ自然に読み取る方法に対応しており、木のコピー、シリアライズ、前置記法の式の評価などに使用されます。再帰による実装は非常に短く書けますが、木の高さをhとすると、深さO(h)の呼び出しスタックを構築します。
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]再帰による中間順走査
中間順走査では、左部分木、根、右部分木の順に訪問します。二分探索木では、中間順走査によって必ずソート済みの列が得られます。この性質は、BSTの検証、k番目に小さい要素、BSTからソート済み配列への変換などの問題で利用されます。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!再帰による後行順走査
後行順走査では、現在のノードより先に両方の子ノードを処理します。この下から上への順序は、親の計算が子の結果に依存する場合に自然です。たとえば、部分木のサイズの計算、木の削除、式木の評価などで使われます。情報を上方向へ渡す木の問題の多くは、暗黙的に後行順のロジックを使用します。
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]スタックを使った反復的な先行順走査
再帰の深さ制限を避けるには、明示的なスタックを使ってDFSを反復的に実装します。先行順では、まず根をプッシュし、各反復でノードをポップして記録した後、右の子、左の子の順にプッシュします（左を先に処理するため、右を先にプッシュします）。これは呼び出しスタックのLIFO動作を再現する方法であり、Pythonのデフォルトの再帰上限1000では処理できない深い木に対する定番のアプローチです。
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]スタックを使った反復的な中間順走査
反復的な中間順走査は、やや複雑です。スタックとポインタcurrを使い、可能な限り左へ進みながらすべてのノードをプッシュします。これ以上左へ進めなくなったらポップしてノードを記録し、その後右へ進みます。この左端までnullになるまでプッシュし、ポップして処理し、その後右へ進むパターンは、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]2つのスタックを使った反復的な後行順走査
反復的な後行順走査には、便利なテクニックがあります。変更した先行順（根 → 右 → 左）で走査し、結果を逆順に収集します。根をプッシュし、ポップして結果の先頭に追加し、左、右の順にプッシュします。反転することで、根・右・左が左・右・根に変わり、これが後行順になります。別の方法として、prevポインタを使い、1つのスタックで直前に訪問したノードを追跡することもできます。
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]どの走査方法を選ぶべきか
適切な走査方法を選べることは、面接で重要な評価ポイントです。子ノードより先に親を処理する必要がある場合（木のシリアライズや構造のコピー）は先行順を使います。BSTでは中間順を使い、ソート順になる性質を利用します。両方の子に依存する値（高さ、直径、部分木の合計など）を計算する場合は後行順を使います。最短経路やレベルごとのグループ化の問題では、BFSが適しています。
# 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走査：O(1)空間の中間順走査
Morris走査では、木を一時的に変更することで、空間計算量O(1)の中間順走査を実現します。左部分木を持つ各ノードについて、中間順の先行ノード（左部分木の最も右にあるノード）を探し、その右ポインタを現在のノードへ戻るように接続します。訪問後に、その接続を元に戻します。この高度なテクニックは、面接官から「追加の空間O(1)で実装できますか」と聞かれるような、最上位企業の面接で出題されます。
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]走査結果から木を再構築する
先行順と中間順の配列が与えられれば、元の木を再構築できます。先行順の最初の要素は必ず根です。その根を中間順の配列から探すと、左側にあるすべての要素が左部分木に、右側にあるすべての要素が右部分木に属します。これを部分配列に対して再帰的に適用します。ハッシュマップによるインデックス検索を使えば、時間計算量は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 20走査の時間計算量と空間計算量のまとめ
3種類のDFS走査はすべて、各ノードをちょうど1回訪問するため、時間計算量O(n)です。空間計算量は、木の高さをhとしてO(h)です。平衡木ではO(log n)、偏った木ではO(n)になります（呼び出しスタックまたは明示的なスタックによるものです）。反復的な実装ではPythonの再帰上限を回避できますが、漸近的な空間計算量は同じです。Morris走査は、木の右ポインタを再利用することで、独自に空間計算量O(1)を実現します。
# 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')理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、3種類のDFS走査順序（先行順、中間順、後行順）とそれぞれを選ぶ場面、明示的なスタックを使った再帰的および反復的な実装、そしてMorrisのO(1)空間テクニックを学びました。次は、二分木の直径、高さ、平衡性の計算について学びます。
よくある質問
「in-order、pre-order、post-order DFS」レッスンは無料ですか？
はい。「in-order、pre-order、post-order DFS」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「in-order、pre-order、post-order DFS」で何を学びますか？
3種類すべてのDFS走査を、再帰と明示的なスタックを使う反復処理で実装し、それぞれの順序が役立つ場面を説明します。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「in-order、pre-order、post-order DFS」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- TreeNodeクラスとレベル順BFS
- in-order、pre-order、post-order DFS
- 直径、高さ、平衡木
- パスの合計と最近共通祖先