이진 탐색 트리(Binary Search Tree)의 후위 순회(postorder) 시퀀스가 주어졌을 때, 이를 기반으로 원래의 트리를 복원하는 방법을 알아보겠습니다. 예를 들어 후위 순회 결과가 [9,15,7,20,3]이라면 다음과 같은 트리가 생성됩니다.
핵심 아이디어
일반적인 이진 트리를 복원하려면 보통 전위(preorder) 또는 후위(postorder) 순회와 함께 중위 순회(inorder) 결과가 필요합니다. 하지만 이진 탐색 트리는 특별한 성질을 가지고 있습니다.
이진 탐색 트리의 중위 순회 결과는 항상 오름차순으로 정렬된 형태라는 점입니다. 따라서 주어진 후위 순회 배열을 정렬하면 그것이 곧 중위 순회 배열이 됩니다. 덕분에 후위 순회 정보만으로 트리를 완전히 복원할 수 있습니다.
알고리즘 단계
중위 순회 = 후위 순회 리스트를 정렬한 결과로 정의합니다.
build_tree()메서드를 정의합니다. 이 메서드는 중위 순회와 후위 순회 두 리스트를 인자로 받습니다.중위 순회 리스트가 비어 있지 않은 경우:
root:= 후위 순회의 마지막 값으로 트리 노드를 생성하고, 해당 요소를 리스트에서 제거합니다.ind:= 중위 순회 리스트에서 root 값의 인덱스를 찾습니다.root의 오른쪽 자식 :=
build_tree()(중위 순회의 ind+1부터 끝까지, 후위 순회)로 재귀 호출합니다.root의 왼쪽 자식 :=
build_tree()(중위 순회의 0부터 ind-1까지, 후위 순회)로 재귀 호출합니다.
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()
postorder = [3,9,20,15,7]
inorder = list(sorted([3,9,20,15,7]))
print_tree(ob1.buildTree(inorder, postorder))
입력
[9,3,15,20,7]
[9,15,7,20,3]
출력
[3,7,9,15,20]
성능 분석 및 최적화 팁
위 구현은 각 재귀 호출마다 index() 검색과 리스트 슬라이싱이 발생하므로 평균적으로 O(n²)의 시간 복잡도를 가집니다. 노드 개수가 많다면 다음과 같이 개선할 수 있습니다.
값과 인덱스를 미리 매핑한 딕셔너리(해시맵)를 사용하면 인덱스 조회를 O(1)로 줄일 수 있습니다.
슬라이싱 대신 시작·끝 인덱스만 넘기면 불필요한 리스트 복사 비용을 없애 전체 시간 복잡도를 O(n)으로 개선할 수 있습니다.