문제 개요
주어진 전위 순회(preorder traversal) 결과와 일치하는 이진 탐색 트리(Binary Search Tree, BST)를 만들어야 하는 문제입니다. 예를 들어 전위 순회가 [8,5,1,7,10,12]로 주어졌다면, 출력은 [8,5,10,1,7,null,12]가 되며, 이는 다음과 같은 트리 구조를 의미합니다.
해결 접근 방법
이 문제는 스택(stack)을 활용하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 전위 순회 리스트의 첫 번째 노드를 루트(root)로 설정합니다.
- 빈 스택을 만들고 루트를 스택에 push합니다.
- 전위 순회 리스트의 두 번째 요소부터 마지막까지 각 요소 i에 대해 다음을 수행합니다.
- i 값을 가지는 새 노드를 생성합니다.
- i의 값이 스택 최상단(top) 노드의 값보다 작다면:
- 스택 최상단 노드의 왼쪽 자식으로 i를 연결합니다.
- i를 스택에 push합니다.
- 그렇지 않다면(즉, i의 값이 더 크거나 같다면):
- 스택이 비어 있지 않고, 스택 최상단 노드의 값이 i보다 작은 동안 반복합니다.
- last := 스택 최상단 노드
- 스택에서 pop합니다.
- 마지막으로 pop한 노드(last)의 오른쪽 자식으로 i를 연결합니다.
- i를 스택에 push합니다.
- 스택이 비어 있지 않고, 스택 최상단 노드의 값이 i보다 작은 동안 반복합니다.
- 루트 노드를 반환합니다.
이 알고리즘은 BST의 성질을 활용합니다. 전위 순회에서 어떤 값이 스택 최상단 값보다 작으면 왼쪽 서브트리에 속하고, 더 큰 값이 나오면 그보다 작은 값들을 모두 pop하여 해당 노드의 오른쪽 자식으로 붙이는 방식입니다.
구현 코드
아래 Python 구현을 통해 더 잘 이해할 수 있습니다.
class Solution(object):
def bstFromPreorder(self, preorder):
"""
:type preorder: List[int]
:rtype: TreeNode
"""
root = TreeNode(preorder[0])
stack = [root]
for i in preorder[1:]:
i = TreeNode(i)
if i.val < stack[-1].val:
stack[-1].left = i
stack.append(i)
else:
while stack and stack[-1].val < i.val:
last = stack.pop(-1)
last.right = i
stack.append(i)
return root실행 결과
입력:
[8,5,1,7,10,12]
출력:
[8,5,10,1,7,null,12]
복잡도 분석
- 시간 복잡도: O(n) — 각 노드는 최대 한 번 push되고 한 번 pop됩니다.
- 공간 복잡도: O(n) — 최악의 경우(오름차순 정렬된 입력) 스택에 모든 노드가 저장될 수 있습니다.