[Iterative DFS] 145. Binary Tree Postorder Traversal

145. Binary Tree Postorder Traversal

 

재귀 방법

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # 후위 순회: 왼쪽 -> 오른쪽 -> 자신
        if not root:
            return []  # 트리가 비어있으면 빈 리스트 반환

        res = []  # 결과를 저장할 리스트

        def dfs(node):
            # 왼쪽 자식 방문
            if node.left:
                dfs(node.left)
            # 오른쪽 자식 방문
            if node.right:
                dfs(node.right)
            # 마지막에 자기 자신 추가
            res.append(node.val)

        dfs(root)  # 루트 노드부터 시작
        return res

 

Iterative DFS

 

• stack: 실제 노드를 담는 스택
• visit: 각 노드가 "재방문했는지 여부"를 담는 스택 (True면 자신 처리할 차례)
• res: 결과 리스트

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        # 후위 순회: 왼쪽 → 오른쪽 → 자신
        # 재귀 없이 구현하기 위해 스택과 방문 여부 배열을 함께 사용

        stack = [root]       # 노드를 저장할 스택 (초기에 루트 넣음)
        visit = [False]      # 해당 노드의 방문 여부 (False: 처음, True: 재방문 시)
        res = []             # 결과를 저장할 리스트

        while stack:
            cur, v = stack.pop(), visit.pop()  # 노드와 해당 노드의 방문 여부를 꺼냄

            if cur:  # 노드가 None이 아닐 때만 처리
                if v:
                    # 자식 노드들을 이미 처리한 후 재방문한 경우
                    # → 이제 자기 자신을 처리할 차례
                    res.append(cur.val)
                else:
                    # 처음 방문한 노드인 경우
                    # 후위 순회를 위해 "자신 → 오른쪽 → 왼쪽" 순서로 스택에 넣음
                    # 이 순서대로 넣으면 나중에 꺼낼 때 "왼쪽 → 오른쪽 → 자신" 순서가 됨

                    stack.append(cur)        # 자기 자신을 다시 push (나중에 재방문 처리용)
                    visit.append(True)       # 재방문 시 True로 처리되도록 설정

                    stack.append(cur.right)  # 오른쪽 자식 push
                    visit.append(False)      # 처음 방문이므로 False

                    stack.append(cur.left)   # 왼쪽 자식 push
                    visit.append(False)      # 처음 방문이므로 False

        return res  # 후위 순회 결과 반환

✅ 요약

• **두 개의 스택(stack, visit)**을 사용해서 재귀 호출 없이 후위 순회를 구현함.
• "자기 자신을 두 번 스택에 넣는다"는 아이디어를 기반으로,
  한 번은 자식 방문용, 한 번은 자기 자신 처리용으로 활용함.
• True일 때만 값을 결과에 추가하고,
  False일 때는 자식 노드들을 먼저 스택에 넣음.

튜플 (노드, 방문 여부) 형태로 하나의 스택에 합친 버전

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []

        stack = [(root, False)]
        res = []

        while stack:
            node, visited = stack.pop()
            if node:
                if visited:
                    res.append(node.val)
                else:
                    stack.append((node, True))
                    stack.append((node.right, False))
                    stack.append((node.left, False))
        return res

 

https://youtu.be/QhszUQhGGlA