문제 개요
단일 연결 리스트(singly linked list)가 주어졌을 때, 다음 규칙에 따라 이를 이진 트리(binary tree)로 변환하는 것이 목표입니다.
- 연결 리스트의 머리 노드(head)는 트리의 루트(root)가 됩니다.
- 이후의 각 노드는 값이 부모 노드보다 작으면 왼쪽 자식으로, 그렇지 않으면 오른쪽 자식으로 배치됩니다.
예를 들어 입력이 [2, 1, 3, 4, 0, 5]라면 변환 결과는 다음과 같습니다.
- 2가 루트가 되고, 1은 2보다 작으므로 왼쪽 자식이 됩니다.
- 3은 1보다 크므로 1의 오른쪽 자식, 4는 3보다 크므로 3의 오른쪽 자식이 됩니다.
- 0은 4보다 작으므로 4의 왼쪽 자식, 5는 0보다 크므로 0의 오른쪽 자식이 됩니다.
풀이 접근 방법
이 문제는 재귀 호출을 활용하면 간단하게 해결할 수 있습니다. 핵심 로직을 단계별로 정리하면 다음과 같습니다.
- solve() 함수를 정의하고, 연결 리스트의 노드(node)를 매개변수로 전달받습니다.
- node가 null이면 null을 반환합니다. (재귀 호출의 종료 조건)
- node의 값과 동일한 값을 가지는 트리 노드를 생성하여 root로 지정합니다.
- node의 다음 노드(next)가 존재하면 다음과 같이 분기합니다.
- next의 값이 현재 node의 값보다 작으면 → root.left = solve(node.next)
- 그렇지 않으면 → root.right = solve(node.next)
- 완성된 root를 반환합니다.
즉, 연결 리스트를 한 번씩 순회하면서 각 노드를 트리 노드로 만들고, 바로 앞 노드와의 값 비교 결과에 따라 왼쪽 또는 오른쪽 자식으로 연결하는 방식입니다.
구현 예제
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
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:
def solve(self, node):
if not node:
return None
root = TreeNode(node.val)
if node.next:
if node.next.val < node.val:
root.left = self.solve(node.next)
else:
root.right = self.solve(node.next)
return root
ob = Solution()
L = make_list([2, 1, 3, 4, 0, 5])
print_tree(ob.solve(L))
입력
[2,1,3,4,0,5]
출력
1, 3, 0, 5, 4, 2,
동작 원리와 복잡도
위 출력은 완성된 트리를 중위 순회(inorder traversal)한 결과입니다. 재귀 함수 solve()는 연결 리스트의 각 노드를 정확히 한 번씩 방문하며, 노드마다 상수 번의 비교와 대입만 수행하므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 재귀 호출 깊이가 연결 리스트의 길이에 비례하여 O(n)입니다.