이진 트리의 중위 순회(inorder)와 후위 순회(postorder) 결과가 주어졌을 때, 이 두 시퀀스만으로 원래의 트리를 복원할 수 있습니다.
예를 들어 후위 순회가 [9, 15, 7, 20, 3]이고 중위 순회가 [9, 3, 15, 20, 7]이라면, 다음과 같은 이진 트리가 생성됩니다.
핵심 아이디어
후위 순회는 왼쪽 → 오른쪽 → 루트 순서로 노드를 방문하므로, 리스트의 마지막 값이 항상 루트입니다. 또한 중위 순회는 왼쪽 → 루트 → 오른쪽 순서이므로, 루트 값을 기준으로 중위 순회 리스트를 나누면 왼쪽 서브트리와 오른쪽 서브트리의 노드들을 구분할 수 있습니다. 이 성질을 재귀적으로 적용하면 전체 트리를 복원할 수 있습니다.
알고리즘 단계
build_tree()메서드를 정의하고, 중위 순회 리스트(inorder)와 후위 순회 리스트(postorder)를 인자로 받습니다.- inorder 리스트가 비어 있지 않은 경우:
root:= postorder의 마지막 값으로 트리 노드를 생성한 뒤, 해당 요소를 리스트에서 제거합니다.ind:= inorder 리스트에서 root 데이터가 위치한 인덱스입니다.- root의 오른쪽 자식 :=
build_tree(inorder[ind+1:], postorder) - root의 왼쪽 자식 :=
build_tree(inorder[:ind], postorder)
- root를 반환합니다.
구현 예제
다음 코드를 통해 더 잘 이해해 보겠습니다.
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, inorder, postorder):
if inorder:
root = TreeNode(postorder.pop())
ind = inorder.index(root.data)
root.right = self.buildTree(inorder[ind+1:], postorder)
root.left = self.buildTree(inorder[:ind], postorder)
return root
ob1 = Solution()
print_tree(ob1.buildTree([9,3,15,20,7], [9,15,7,20,3]))
입력
[9,3,15,20,7]
[9,15,7,20,3]
출력
[9,3,15,20,7]
동작 원리 상세 설명
1. 후위 순회의 마지막 값 3이 루트 노드가 됩니다.
2. 중위 순회 [9, 3, 15, 20, 7]에서 3의 위치(인덱스 1)를 찾습니다.
3. 인덱스 1을 기준으로 왼쪽 부분 [9]는 왼쪽 서브트리, 오른쪽 부분 [15, 20, 7]은 오른쪽 서브트리에 해당합니다.
4. 각 서브트리에 대해 같은 과정을 재귀적으로 반복하면 전체 트리가 완성됩니다.
시간 복잡도
매 재귀 호출마다 index()로 값을 찾기 때문에 위 구현의 시간 복잡도는 O(n²)입니다. 해시 맵(딕셔너리)을 사용해 값의 인덱스를 미리 저장하면 O(n)으로 최적화할 수 있습니다.