문제 소개
이진 트리의 중위 순회(inorder traversal)와 후위 순회(postorder traversal) 결과가 주어졌을 때, 이 두 순회 정보만으로 원래의 이진 트리를 다시 복원하는 것이 목표입니다.
예를 들어 후위 순회가 [9, 15, 7, 20, 3]이고 중위 순회가 [9, 3, 15, 20, 7]이라면, 아래 그림과 같은 이진 트리가 완성됩니다.
알고리즘 접근 방법
핵심은 두 순회 방식이 가진 고유한 성질을 활용하는 것입니다.
- 후위 순회는 '왼쪽 → 오른쪽 → 루트' 순서로 방문하므로, 후위 순회 배열의 마지막 원소가 항상 루트입니다.
- 중위 순회는 '왼쪽 → 루트 → 오른쪽' 순서로 방문하므로, 중위 순회 배열에서 루트 값을 기준으로 왼쪽 구간은 왼쪽 서브트리, 오른쪽 구간은 오른쪽 서브트리에 해당합니다.
이 성질을 바탕으로 다음 단계를 재귀적으로 반복하면 트리 전체를 구성할 수 있습니다.
- 후위 순회 배열의 마지막 값을 꺼내 루트 노드로 생성하고, 배열에서 제거합니다.
- 중위 순회 배열에서 루트 값의 인덱스(root_index)를 찾습니다.
- root_index를 기준으로 나뉜 구간들을 이용해 오른쪽 서브트리와 왼쪽 서브트리를 재귀 호출로 구성합니다. 후위 순회 배열을 뒤에서부터 소모하므로 오른쪽 서브트리를 먼저 처리해야 한다는 점에 유의하세요.
구현 예제
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def print_tree(root):
# 중위 순회 방식으로 트리 출력
if root is not None:
print_tree(root.left)
print(root.data, end=', ')
print_tree(root.right)
class Solution(object):
def buildTree(self, postorder, inorder):
if inorder:
root = TreeNode(postorder.pop()) # 후위 순회의 마지막 값이 루트
root_index = inorder.index(root.data) # 중위 순회에서 루트 위치 탐색
root.right = self.buildTree(postorder, inorder[root_index+1:]) # 오른쪽 서브트리 먼저
root.left = self.buildTree(postorder, inorder[:root_index]) # 왼쪽 서브트리
return root
ob1 = Solution()
print_tree(ob1.buildTree([9, 15, 7, 20, 3], [9, 3, 15, 20, 7]))
입력
postorder = [9, 15, 7, 20, 3] inorder = [9, 3, 15, 20, 7]
출력
9, 3, 15, 20, 7,
동작 과정 상세 분석
1. 후위 순회의 마지막 값인 3이 전체 트리의 루트가 됩니다.
2. 중위 순회 [9, 3, 15, 20, 7]에서 3의 위치를 기준으로 나누면, 왼쪽 구간 [9]는 왼쪽 서브트리, 오른쪽 구간 [15, 20, 7]은 오른쪽 서브트리가 됩니다.
3. 같은 과정을 반복하면 20이 오른쪽 서브트리의 루트로 결정되고, 15와 7이 각각 20의 왼쪽·오른쪽 자식으로 배치됩니다.
4. 최종적으로 완성된 트리를 중위 순회로 출력하면 입력한 중위 순회 결과와 동일한 것을 확인할 수 있습니다.
복잡도 및 최적화 팁
위 구현은 매 재귀 호출마다 index() 탐색과 리스트 슬라이싱이 발생하므로, 편향된 트리에서는 최악의 경우 O(n²)의 시간 복잡도를 가집니다. 중위 순회 값의 인덱스를 해시 맵(딕셔너리)에 미리 저장해 두고, 슬라이싱 대신 시작·끝 포인터를 넘기는 방식으로 개선하면 O(n)까지 최적화할 수 있습니다.