개요
이진 탐색 트리(Binary Search Tree, BST)의 후위 순회(postorder traversal) 결과가 하나 주어졌을 때, 이를 역추적하여 원래의 이진 탐색 트리를 복원하는 문제입니다.
예를 들어 입력이 [6, 12, 10, 55, 45, 15]라면, 다음과 같은 BST가 만들어집니다.
알고리즘 접근 방식
후위 순회는 왼쪽 → 오른쪽 → 루트 순서로 방문하기 때문에, 배열의 마지막 요소가 곧 트리의 루트가 됩니다. 배열을 끝에서부터 앞으로 거꾸로 순회하면서 스택(stack)을 활용하면 각 노드의 부모-자식 관계를 효율적으로 결정할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 배열을 뒤에서부터 읽으면, 값이 점점 작아지다가 커지는 지점에서 왼쪽 서브트리로 넘어갑니다.
- 스택에는 현재 경로상의 노드들이 저장되며, 새 노드의 값보다 큰 노드들을 스택에서 꺼내면 그중 마지막으로 꺼낸 노드가 새 노드의 부모(왼쪽 자식 연결 대상)가 됩니다.
단계별 풀이 과정
solve()함수를 정의하고 후위 순회 배열postorder를 전달합니다.n := postorder의 길이로 설정합니다.root:= 후위 순회의 마지막 요소로 새 트리 노드를 생성합니다.stk:= 빈 스택을 준비한 뒤root를 삽입합니다.i := n - 2로 설정하고,i >= 0인 동안 반복합니다.x:= 값이postorder[i]인 새 노드를 생성합니다.- 스택이 비어 있지 않고
postorder[i]가 스택 최상단 값보다 작은 동안, 최상단 노드를temp에 저장하고 pop 합니다. temp가 null이 아니라면temp.left := x로 왼쪽 자식에 연결합니다.- 그렇지 않다면 현재 스택 최상단 노드의 오른쪽 자식으로
x를 연결합니다. x를 스택에 삽입하고i를 1 감소시킵니다.
- 반복이 끝나면
root를 반환합니다.
Python 구현 코드
아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.
class TreeNode:
def __init__(self, data = 0):
self.val = data
self.left = None
self.right = None
def solve(postorder):
n = len(postorder)
root = TreeNode(postorder[n - 1])
stk = []
stk.append(root)
i = n - 2
while (i >= 0):
x = TreeNode(postorder[i])
temp = None
while (len(stk) > 0 and postorder[i] < stk[-1].val):
temp = stk[-1]
stk.pop()
if (temp != None):
temp.left = x
else:
stk[-1].right = x
stk.append(x)
i = i - 1
return root
def build_tree(postorder):
return solve(postorder)
def inord(node):
if node:
inord(node.left)
print(node.val, end = " ")
inord(node.right)
postorder = [6, 12, 10, 55, 45, 15]
root = build_tree(postorder)
print("Inorder traversal:", end = " ")
inord(root)입력
[6, 12, 10, 55, 45, 15]
출력
6 10 12 15 45 55
동작 원리 설명
결과로 출력된 중위 순회(inorder traversal) 값 6 10 12 15 45 55는 오름차순으로 정렬되어 있습니다. 중위 순회가 오름차순이라는 것은 트리가 올바른 이진 탐색 트리임을 의미하므로, 알고리즘이 정확하게 동작했음을 확인할 수 있습니다.
이 방법은 각 노드를 한 번씩만 방문하고, 각 노드도 최대 한 번 push/pop 되기 때문에 시간 복잡도는 O(n), 공간 복잡도는 스택 깊이에 따라 최악의 경우 O(n)입니다. 재귀를 사용하지 않으므로 깊은 트리에서도 스택 오버플로우 걱정 없이 안전하게 동작한다는 장점이 있습니다.