문제 개요
이진 검색 트리(Binary Search Tree)가 주어졌을 때, 같은 노드 값들을 가지면서 균형이 잡힌 새로운 이진 검색 트리를 만들어야 합니다.
여기서 '균형 잡힌 트리'란 모든 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 깊이 차이가 1을 넘지 않는 경우를 의미합니다. 결과가 여러 개일 수 있다면 그중 아무거나 반환하면 됩니다.
예를 들어 다음과 같은 트리가 입력으로 주어졌다고 가정해 보겠습니다.
해결 접근 방법
핵심 아이디어는 간단합니다. 이진 검색 트리를 중위 순회(Inorder Traversal)하면 항상 오름차순으로 정렬된 값 배열을 얻을 수 있습니다. 이 정렬된 배열을 이용하면 균형 잡힌 BST를 쉽게 재구성할 수 있습니다.
구체적인 단계는 다음과 같습니다.
inorder()메서드를 정의하여 중위 순회 결과를 배열에 저장합니다.construct()메서드를 정의하고, low와 high 인덱스를 인자로 받습니다.low > high라면 null을 반환합니다(재귀 종료 조건).mid := low + (high - low) / 2로 구간의 중간 인덱스를 계산합니다.arr[mid]값을 가지는 새 노드를 루트로 생성합니다.루트의 왼쪽 자식은
construct(low, mid - 1), 오른쪽 자식은construct(mid + 1, high)로 재귀적으로 설정합니다.루트를 반환합니다.
메인 메서드에서
inorder()를 호출한 뒤,construct(0, arr.size() - 1)을 호출하여 최종 트리를 얻습니다.
중간 값을 항상 루트로 선택하기 때문에 왼쪽과 오른쪽 서브트리의 노드 수 차이가 최대 1로 유지되며, 이것이 곧 균형 잡힌 트리가 되는 원리입니다.
C++ 구현 예제
아래 코드를 통해 더 잘 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
void tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue<TreeNode *> q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
} else {
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr->val == 0 || curr == NULL){
cout << "null" << ", ";
}else{
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
vector <int> arr;
void inorder(TreeNode* node){
if(!node || node->val == 0) return;
inorder(node->left);
arr.push_back(node->val);
inorder(node->right);
}
TreeNode* construct(int low, int high){
if(low > high) return NULL;
int mid = low + (high - low) / 2;
TreeNode* root = new TreeNode(arr[mid]);
root->left = construct(low, mid - 1);
root->right = construct(mid + 1, high);
return root;
}
TreeNode* balanceBST(TreeNode* root) {
inorder(root);
return construct(0, (int)arr.size() - 1);
}
};
main(){
vector<int> v = {1,NULL,2,NULL,NULL,NULL,3,NULL,NULL,NULL,NULL,NULL,NULL,NULL,4};
TreeNode *root = make_tree(v);
Solution ob;
tree_level_trav(ob.balanceBST(root));
}입력
[1,NULL,2,NULL,NULL,NULL,3,NULL,NULL,NULL,NULL,NULL,NULL,NULL,4]
출력
[2, 1, 3, 4]
동작 과정 설명
입력 트리를 중위 순회하면 정렬된 배열 [1, 2, 3, 4]가 생성됩니다. 이후 construct() 함수가 이 배열의 중간값을 반복적으로 루트로 삼아 트리를 재구성합니다.
- 전체 구간 [0, 3]에서 mid = 1이므로 값 2가 루트가 됩니다.
- 왼쪽 구간 [0, 0]에서 값 1이 왼쪽 자식이 됩니다.
- 오른쪽 구간 [2, 3]에서 mid = 2이므로 값 3이 오른쪽 자식이 됩니다.
- 구간 [3, 3]에서 값 4가 3의 오른쪽 자식이 됩니다.
결과적으로 출력 [2, 1, 3, 4]와 같은 균형 잡힌 트리가 완성됩니다.
시간 및 공간 복잡도
시간 복잡도: O(n) — 중위 순회와 트리 재구성 모두 모든 노드를 한 번씩 방문합니다.
공간 복잡도: O(n) — 정렬된 값을 저장하는 배열과 재귀 호출 스택이 필요합니다.