이진 탐색 트리(Binary Search Tree)가 주어졌을 때, 이를 레벨 순서(level order) 순회 방식으로 단일 연결 리스트(singly linked list)로 변환하는 문제를 파이썬으로 해결해 보겠습니다.
예를 들어 다음과 같은 이진 트리가 입력으로 주어지면,
출력 결과는 다음과 같습니다.
[5, 4, 10, 2, 7, 15]
문제 해결 접근 방법
이 문제는 BFS(너비 우선 탐색) 방식의 큐(queue)를 활용하면 간단하게 해결할 수 있습니다. 알고리즘의 동작 순서는 다음과 같습니다.
- 더미(dummy) 헤드 노드 하나를 생성합니다.
- 현재 노드를 가리킬 포인터 currNode를 헤드로 초기화합니다.
- 루트 노드를 담은 큐 q를 준비합니다.
- 큐가 빌 때까지 다음 과정을 반복합니다.
- 큐에서 맨 앞의 원소를 꺼냅니다.
- 꺼낸 노드가 null이 아니라면, 해당 노드의 값을 가진 새 연결 리스트 노드를 currNode 뒤에 연결합니다.
- currNode를 새로 만든 노드로 이동시킵니다.
- 현재 트리 노드의 왼쪽 자식과 오른쪽 자식을 큐 뒤에 추가합니다.
- 모든 순회가 끝나면 더미 헤드의 next를 반환합니다.
이 방식은 트리의 같은 레벨에 있는 노드들을 왼쪽에서 오른쪽 순서대로 처리하므로, 결과 연결 리스트도 자연스럽게 레벨 순서대로 값이 배치됩니다.
파이썬 구현 코드
아래 예제 코드를 통해 실제 구현을 확인해 보겠습니다.
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
class TreeNode:
def __init__(self, data, left=None, right=None):
self.val = data
self.left = left
self.right = right
def print_list(head):
ptr = head
print('[', end='')
while ptr:
print(ptr.val, end=', ')
ptr = ptr.next
print(']')
class Solution:
def solve(self, root):
head = ListNode(None)
currNode = head
q = [root]
while q:
curr = q.pop(0)
if curr:
currNode.next = ListNode(curr.val)
currNode = currNode.next
q.append(curr.left)
q.append(curr.right)
return head.next
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(2)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
head = ob.solve(root)
print_list(head)입력
root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(10) root.left.left = TreeNode(2) root.right.left = TreeNode(7) root.right.right = TreeNode(15)
출력
[5, 4, 10, 2, 7, 15]
코드 설명 및 시간 복잡도
ListNode 클래스는 연결 리스트의 각 노드를 나타내고, TreeNode 클래스는 이진 트리의 노드를 나타냅니다. solve() 메서드에서는 더미 헤드 노드를 사용해 첫 번째 실제 노드부터 순차적으로 연결하므로, 반환 시 head.next만 돌려주면 됩니다.
큐에서 원소를 꺼낼 때 pop(0)을 사용했는데, 리스트의 맨 앞 원소 제거는 O(n)의 비용이 듭니다. 성능을 개선하려면 collections.deque의 popleft()를 사용하는 것이 좋습니다.
- 시간 복잡도: O(n) — 트리의 모든 노드를 한 번씩 방문합니다.
- 공간 복잡도: O(n) — 큐와 결과 연결 리스트에 최대 n개의 노드가 저장됩니다.
이처럼 큐 기반의 레벨 순서 순회를 활용하면 이진 트리를 손쉽게 연결 리스트 형태로 변환할 수 있습니다.