문제 개요
서로 다른 정수 값으로 구성된 이진 검색 트리(Binary Search Tree, BST)의 루트 노드가 주어집니다. 이 트리를 더 큰 합 트리(Greater Sum Tree)로 변환하는 것이 목표입니다. 즉, 모든 노드의 새로운 값은 원래 트리에서 그 노드의 값보다 크거나 같은 모든 노드 값의 합이 되어야 하며, 변환 후에도 BST의 기본 성질(왼쪽 자식 < 부모 < 오른쪽 자식)은 그대로 유지되어야 합니다.
예를 들어 입력 트리가 다음과 같다면 −
변환된 출력 트리는 다음과 같습니다 −
값이 4인 루트 노드를 예로 들면, 원래 트리에서 4보다 크거나 같은 값은 4, 5, 6, 7, 8이므로 이들의 합인 30이 루트의 새로운 값이 됩니다.
접근 방법: 역방향 중위 순회(Reverse In-order Traversal)
BST의 일반적인 중위 순회는 왼쪽 → 루트 → 오른쪽 순서로 진행되며, 이 경우 값이 오름차순으로 방문됩니다. 하지만 이 문제는 각 노드보다 크거나 같은 값들의 누적합이 필요하므로, 순회 방향을 거꾸로 뒤집는 것이 핵심 아이디어입니다. 즉, 오른쪽 → 루트 → 왼쪽 순서로 트리를 탐색하면 가장 큰 값부터 차례대로 누적할 수 있습니다.
구체적인 해결 단계는 다음과 같습니다 −
전역 누적합 변수 global을 0으로 초기화합니다.
루트를 인자로 받는 재귀 함수 solve()를 정의합니다.
루트의 오른쪽 자식이 NULL이 아니라면, 먼저 solve(오른쪽 자식)를 호출합니다.
global에 현재 노드의 값을 더한 뒤, 그 결과를 현재 노드의 새로운 값으로 저장합니다.
루트의 왼쪽 자식이 NULL이 아니라면, solve(왼쪽 자식)를 호출합니다.
루트를 반환합니다.
이 순서로 탐색하면 각 노드를 방문하는 시점의 global 값이 곧 "그 노드보다 크거나 같은 모든 값의 합"이 되므로, 단 한 번의 순회만으로 전체 트리를 변환할 수 있습니다.
예제 코드 (C++)
아래 구현을 통해 더 잘 이해해 보겠습니다 −
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
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 == NULL || curr->val == 0){
cout << "null" << ", ";
}else{
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
int global = 0;
TreeNode* bstToGst(TreeNode* root) {
if(root->right)bstToGst(root->right);
if(root->val != 0)
root->val = global = global + root->val;
if(root->left)bstToGst(root->left);
return root;
}
};
main(){
vector<int> v =
{4,1,6,1,2,5,7,NULL,NULL,NULL,3,NULL,NULL,NULL,8};
TreeNode *root = make_tree(v);
Solution ob;
tree_level_trav(ob.bstToGst(root));
}입력
[4,1,6,1,2,5,7,null,null,null,3,null,null,null,8]
출력
[30, 36, 21, 37, 35, 26, 15, null, null, null, 33, null, null, null, 8]
복잡도 분석
이 풀이는 트리의 모든 노드를 정확히 한 번씩만 방문하므로 시간 복잡도는 O(N)(N은 노드의 개수)입니다. 공간 복잡도는 재귀 호출 스택의 깊이에 비례하여 최악의 경우 O(N), 균형 잡힌 트리라면 O(log N)입니다. 추가적인 자료구조 없이 누적합 변수 하나만 사용하기 때문에 메모리 측면에서도 매우 효율적입니다.