C++에서 요소들이 비내림차순(오름차순)으로 정렬되어 있는 단일 연결 리스트(singly linked list)가 주어졌을 때, 이를 높이 균형 이진 탐색 트리(height balanced BST)로 변환하는 방법을 알아보겠습니다.
예를 들어 연결 리스트가 [-10, -3, 0, 5, 9]와 같이 구성되어 있다면, 이를 변환하여 만들 수 있는 트리는 다음과 같습니다.
문제 해결 접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 연결 리스트가 비어 있으면 null을 반환합니다.
- 리스트의 시작 노드를 매개변수로 받는 재귀 함수 sortedListToBST()를 정의합니다.
- x := 리스트에서 중간 노드(mid) 바로 앞에 있는 노드의 주소
- mid := 리스트의 정확한 중간 노드
- mid가 가진 값으로 새로운 트리 노드를 생성합니다.
- nextStart := mid 노드의 다음 노드
- mid의 next 포인터를 null로 설정하여 리스트를 분리합니다.
- 생성한 노드의 오른쪽 자식 := sortedListToBST(nextStart)
- x가 null이 아니라면, x의 next를 null로 설정하고 생성한 노드의 왼쪽 자식 := sortedListToBST(a)
- 생성한 노드를 반환합니다.
여기서 중간 노드를 찾기 위해 빠른 포인터(fast pointer)와 느린 포인터(slow pointer) 기법을 활용합니다. 빠른 포인터는 한 번에 두 칸씩, 느린 포인터는 한 칸씩 이동하므로, 빠른 포인터가 리스트의 끝에 도달하는 순간 느린 포인터는 정확히 리스트의 중간에 위치하게 됩니다. 이렇게 찾은 중간 노드를 루트로 삼고, 앞부분과 뒷부분 리스트를 재귀적으로 변환하면 자연스럽게 높이 균형이 유지됩니다.
예제 코드
#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));
}
입력
[-10,-3,0,5,9]
출력
-10 -3 0 5 9
코드 설명 및 복잡도 분석
실행 결과를 보면 중위 순회(inorder traversal)한 값이 원래 연결 리스트와 동일한 정렬된 순서로 출력됩니다. 이는 이진 탐색 트리의 특성상 중위 순회를 수행하면 항상 값이 오름차순으로 출력되기 때문이며, 변환이 올바르게 이루어졌음을 의미합니다.
시간 복잡도는 각 재귀 단계마다 리스트 전체를 순회하여 중간 노드를 찾아야 하므로 O(n log n)이며, 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 균형 트리의 높이만큼인 O(log n)입니다.