후위 순회의 역순

순회 방법 정리

1. Pre-order Traversal (전위 순회):
   • 방문 순서: 루트 -> 왼쪽 -> 오른쪽
   • 전위 순회 결과: [1, 2, 4, 5, 3]
2. Post-order Traversal (후위 순회):
   • 방문 순서: 왼쪽 -> 오른쪽 -> 루트
   • 동일한 트리에서 후위 순회 결과: [4, 5, 2, 3, 1]
3. In-order Traversal (중위 순회):
   • 방문 순서: 왼쪽 -> 루트 -> 오른쪽
   • 동일한 트리에서 중위 순회 결과: [4, 2, 5, 1, 3]

 

후위 순회의 역순은

후위 순회(Post-order Traversal)를 수행한 뒤, 그 결과를 뒤집은 순서를 의미합니다.

 

후위 순회(Post-order Traversal)

• 순서: 왼쪽 -> 오른쪽 -> 루트
• 예: 트리 노드의 값이 1, 2, 3, 4, 5라고 하면 후위 순회의 결과는 [4, 5, 2, 3, 1]

후위 순회의 역순

• 후위 순회의 결과를 뒤집습니다.
• 위의 예에서 후위 순회의 역순은 [1, 3, 2, 5, 4]가 됩니다.

구현 방법

후위 순회의 역순을 구하는 두 가지 방법이 있습니다:

 

1. 후위 순회를 수행한 결과를 얻은 뒤, 리스트를 뒤집기

def postorder_reverse(root):
    result = []
    def postorder(node):
        if not node:
            return
        postorder(node.left)
        postorder(node.right)
        result.append(node.val)
    postorder(root)
    return result[::-1]  # 리스트 뒤집기

 

2. 스택을 사용하여 후위 순회의 역순을 직접 계산

후위 순회의 역순은 사실 **전위 순회(Pre-order Traversal)**의 변형으로도 생각할 수 있습니다:

• 전위 순회 순서: 루트 -> 오른쪽 -> 왼쪽
• 이후 결과를 뒤집으면 후위 순회의 역순이 됩니다.

def postorder_reverse(root):
    if not root:
        return []
    stack, result = [root], []
    while stack:
        node = stack.pop()
        result.append(node.val)
        if node.left:
            stack.append(node.left)
        if node.right:
            stack.append(node.right)
    return result[::-1]  # 리스트 뒤집기

 

이 두 가지 방법 모두 동일한 결과를 출력합니다.

상황에 따라 편리한 방식을 선택하면 됩니다!

 

결론

스택을 사용하여 후위 순회의 역순을 직접 계산하는 방법은

**전위 순회를 약간 변형(루트 -> 오른쪽 -> 왼쪽)**한 뒤 결과를 뒤집는 것과 정확히 일치합니다.