Iterative DFS (반복형 깊이 우선 탐색)

지금까지 본 inorder, preorder, postorder 순회 방식은 모두

**Iterative DFS (반복형 깊이 우선 탐색)**입니다.
즉, 재귀 없이 스택(stack) 을 사용해 직접 순서를 제어하면서 깊이 우선 탐색을 구현한 방식이에요.

---

✅ Iterative DFS란?

• DFS (Depth-First Search) = 트리를 아래(깊이)로 먼저 탐색하는 알고리즘
• 일반적으로는 재귀로 많이 구현하지만,
• Stack을 이용해서 반복문으로 구현한 DFS를 Iterative DFS라고 부릅니다.

---

✅ 언제 Iterative DFS를 쓰는가?

상황이유

상황	이유
🔁 재귀 호출이 너무 깊어질 수 있는 경우	Python은 재귀 깊이 제한(기본 1000) 때문에 RecursionError 발생 위험
🧠 재귀보다 명시적 흐름이 필요한 경우	스택 상태를 직접 관리하고 디버깅할 수 있음
📱 인터뷰나 알고리즘 문제에서 재귀 금지	일부 문제는 반드시 반복문만 사용하게 조건이 붙음
🧠 동작 순서를 세밀하게 제어하고 싶은 경우	예: 전위/중위/후위 순회 한꺼번에 처리 등

---

✅ 대표 사용 예시

• 이진 트리 순회 (inorder / preorder / postorder)
• 그래프 DFS 탐색
• 백트래킹을 명시적으로 구현하고 싶은 경우
• 재귀 제한을 피해야 할 대형 트리 문제

---

✅ 장단점 요약

방식장점단점

방식	장점	단점
재귀 DFS	코드가 짧고 직관적	재귀 깊이 제한이 있음
Iterative DFS	스택으로 직접 제어 가능, 안전	코드가 길고 복잡할 수 있음

 

 

이진 트리 순회 알고리즘 (중위, 전위, 후위)

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val       # 노드 값
        self.left = left     # 왼쪽 자식
        self.right = right   # 오른쪽 자식

 

✅ 중위 순회 (Inorder): 왼쪽 → 노드 → 오른쪽

# 중위 순회: 왼쪽 → 자기 자신 → 오른쪽
# 시간, 공간 복잡도: O(n)
def inorder(root):
    stack = []        # 방문 노드 추적용 스택
    curr = root       # 현재 탐색 중인 노드

    while curr or stack:  # 현재 노드가 존재하거나, 스택에 남은 노드가 있을 때까지 반복
        if curr:
            stack.append(curr)  # 왼쪽 끝까지 가기 위해 현재 노드를 스택에 저장
            curr = curr.left    # 왼쪽 자식으로 이동
        else:
            curr = stack.pop()  # 더 이상 왼쪽이 없으면 가장 최근 노드를 꺼냄
            print(curr.val)     # 노드 방문
            curr = curr.right   # 오른쪽 자식으로 이동

✅ 전위 순회 (Preorder): 노드 → 왼쪽 → 오른쪽

# 전위 순회: 자기 자신 → 왼쪽 → 오른쪽
# 시간, 공간 복잡도: O(n)
def preorder(root):
    stack = []       # 오른쪽 자식을 임시 저장할 스택
    curr = root      # 현재 노드

    while curr or stack:
        if curr:
            print(curr.val)         # 먼저 노드 방문
            if curr.right:          # 오른쪽 자식은 나중에 방문해야 하므로 스택에 저장
                stack.append(curr.right)
            curr = curr.left        # 왼쪽 자식으로 먼저 이동
        else:
            curr = stack.pop()      # 왼쪽이 끝나면 스택에서 오른쪽 자식을 꺼내서 처리

 

✅ 후위 순회 (Postorder): 왼쪽 → 오른쪽 → 노드

# 후위 순회: 왼쪽 → 오른쪽 → 자기 자신
# 시간, 공간 복잡도: O(n)
def postorder(root):
    stack = [root]        # 트리를 탐색할 노드 저장
    visit = [False]       # 방문 여부 추적 (False = 아직 처리 전, True = 처리할 차례)

    while stack:
        curr = stack.pop()     # 현재 노드 꺼냄
        visited = visit.pop()  # 방문 여부 꺼냄

        if curr:
            if visited:
                print(curr.val)  # 자식 노드를 모두 처리한 후에 출력
            else:
                # 나중에 다시 이 노드를 방문할 수 있도록 스택에 저장
                stack.append(curr)
                visit.append(True)
                # 후위 순서는 왼쪽 → 오른쪽 → 루트 이므로,
                # 스택에 넣을 때는 거꾸로: 오른쪽 → 왼쪽 순으로 넣기
                stack.append(curr.right)
                visit.append(False)
                stack.append(curr.left)
                visit.append(False)