이진 트리의 전위 순회(preorder) 순서와 중위 순회(inorder) 순서가 주어졌을 때, 이 두 순회 결과만으로 원래의 이진 트리를 다시 만들어야 합니다. 예를 들어 전위 순회가 [3,9,20,15,7]이고 중위 순회가 [9,3,15,20,7]이라면, 다음과 같은 이진 트리가 생성됩니다.
알고리즘 단계
- buildTree 메서드는 전위 순회 리스트와 중위 순회 리스트를 인자로 받습니다.
- 전위 순회의 첫 번째 노드를 루트(root)로 지정하고, 해당 노드를 전위 순회 리스트에서 제거합니다.
- 중위 순회 리스트에서 루트 값(root.val)의 위치를 찾아 root_index에 저장합니다.
- 루트의 왼쪽 자식은 buildTree(preorder, 중위 순회의 0번째부터 root_index 앞까지 부분 리스트)의 결과로 설정합니다.
- 루트의 오른쪽 자식은 buildTree(preorder, 중위 순회의 root_index + 1부터 끝까지 부분 리스트)의 결과로 설정합니다.
동작 원리
이 방법이 성립하는 이유는 두 순회 방식의 특성 때문입니다. 전위 순회는 항상 루트 → 왼쪽 → 오른쪽 순서로 방문하므로, 전위 순회 리스트의 첫 번째 요소가 곧 현재 서브트리의 루트입니다. 반면 중위 순회는 왼쪽 → 루트 → 오른쪽 순서로 방문하기 때문에, 중위 순회 리스트에서 루트 값을 기준으로 왼쪽 부분은 왼쪽 서브트리에, 오른쪽 부분은 오른쪽 서브트리에 속한 노드들입니다. 이 성질을 재귀적으로 반복 적용하면 전체 트리를 복원할 수 있습니다.
예제 코드
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, preorder, inorder):
if inorder:
root = TreeNode(preorder.pop(0))
root_index = inorder.index(root.data)
root.left = self.buildTree(preorder,inorder[:root_index])
root.right = self.buildTree(preorder,inorder[root_index+1:])
return root
ob1 = Solution()
print_tree(ob1.buildTree([3,9,20,15,7], [9,3,15,20,7]))입력
[3,9,20,15,7] [9,3,15,20,7]
출력
9, 3, 15, 20, 7,
시간 복잡도 개선 팁
위 코드는 각 재귀 호출마다 pop(0)과 index() 연산을 수행하므로 최악의 경우 O(n²)의 시간 복잡도를 가집니다. 실무나 코딩 테스트에서는 전위 순회의 현재 위치를 가리키는 포인터와, 값 → 인덱스 매핑을 저장한 해시맵(딕셔너리)을 활용하면 O(n) 시간에 트리를 구성할 수 있으니 참고하면 좋습니다.