오름차순으로 정렬된 단일 연결 리스트(singly linked list)가 주어졌을 때, 이를 높이 균형 이진 검색 트리(height-balanced BST)로 변환하는 것이 목표입니다. 예를 들어 리스트가 [-10, -3, 0, 5, 9]와 같다면, 만들 수 있는 트리의 한 형태는 다음과 같습니다.
해결 접근 방법
핵심 아이디어는 정렬된 리스트의 가운데 원소를 루트로 삼는 것입니다. 가운데 값을 루트로 선택하면 그보다 작은 값들은 모두 왼쪽 절반에, 큰 값들은 모두 오른쪽 절반에 위치하게 되므로 BST의 성질이 자연스럽게 유지됩니다. 또한 매번 리스트를 절반씩 나누어 재귀적으로 트리를 구성하기 때문에 좌우 서브트리의 높이 차이가 최대 1 이내로 유지되어 높이 균형이 보장됩니다.
구체적인 알고리즘은 다음과 같습니다.
- 리스트가 비어 있으면 null을 반환합니다.
- 리스트의 시작 노드를 인자로 받는 재귀 함수 sortedListToBST()를 정의합니다.
- 투 포인터(fast/slow) 기법으로 리스트의 중간 노드(mid)와 그 직전 노드(prev)를 찾습니다.
- mid의 값을 갖는 새로운 트리 노드(node)를 생성합니다.
- nextStart := mid의 다음 노드
- mid->next = NULL로 설정하여 리스트를 두 부분으로 분리합니다.
- node->right := sortedListToBST(nextStart) — 후반부 리스트로 오른쪽 서브트리를 구성합니다.
- prev가 존재하면 prev->next = NULL로 연결을 끊고, node->left := sortedListToBST(a) — 전반부 리스트로 왼쪽 서브트리를 구성합니다.
- node를 반환합니다.
복잡도 분석: 각 재귀 단계마다 중간 노드를 찾기 위해 리스트를 순회해야 하므로 시간 복잡도는 O(n log n)입니다. 재귀 호출 깊이는 트리의 높이에 비례하므로 추가 공간 복잡도는 O(log n)입니다.
C++ 구현 예제
아래 코드를 통해 동작 과정을 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
int val;
ListNode *next;
ListNode(int data){
val = data;
next = NULL;
}
};
ListNode *make_list(vector<int> v){
ListNode *head = new ListNode(v[0]);
for(int i = 1; i<v.size(); i++){
ListNode *ptr = head;
while(ptr->next != NULL){
ptr = ptr->next;
}
ptr->next = new ListNode(v[i]);
}
return head;
}
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};
void inord(TreeNode *root){
if(root != NULL){
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
pair <ListNode*, ListNode*> getMid(ListNode* a){
ListNode* prev = NULL;
ListNode* fast = a;
ListNode* slow = a;
while(fast && fast->next){
fast = fast->next->next;
prev = slow;
slow = slow->next;
}
return {prev, slow};
}
TreeNode* sortedListToBST(ListNode* a) {
if(!a)return NULL;
pair<ListNode*, ListNode*> x = getMid(a);
ListNode* mid = x.second;
TreeNode* Node = new TreeNode(mid->val);
ListNode* nextStart = mid->next;
mid->next = NULL;
Node->right = sortedListToBST(nextStart);
if(x.first){
x.first->next = NULL;
Node->left = sortedListToBST(a);
}
return Node;
}
};
main(){
vector<int> v = {-10,-3,0,5,9};
ListNode *head = make_list(v);
Solution ob;
inord(ob.sortedListToBST(head));
}실행 결과
위 코드는 생성된 BST를 중위 순회(inorder traversal)하여 결과를 출력합니다. BST에서 중위 순회는 항상 오름차순으로 정렬된 값을 출력하므로, 결과가 입력 리스트와 동일한 순서로 나오는지 확인함으로써 트리가 올바르게 구성되었음을 검증할 수 있습니다.
입력
[-10,-3,0,5,9]
출력
-10 -3 0 5 9