C++로 이진 탐색 트리(BST)를 Greater Tree로 변환하는 방법

문제 개요

이진 탐색 트리(Binary Search Tree, BST)가 하나 주어져 있다고 가정해 봅시다. 이 트리를 Greater Tree(그레이터 트리)로 변환해야 하며, 변환 규칙은 다음과 같습니다. 원래 BST의 모든 노드 값을 '원래 키 값 + BST에서 그 키보다 큰 모든 키의 합'으로 변경하는 것입니다.

예를 들어 입력 트리가 다음과 같다면,

출력 결과는 다음과 같습니다.

C++로 이진 탐색 트리(BST)를 Greater Tree로 변환하는 방법

접근 방법: 역중위 순회(Reverse Inorder)

BST에서 일반적인 중위 순회(왼쪽 → 루트 → 오른쪽)를 수행하면 노드 값이 오름차순으로 방문됩니다. 반대로 오른쪽 → 루트 → 왼쪽 순서로 순회하는 역중위 순회를 사용하면 노드를 내림차순으로 방문할 수 있습니다. 이때 방문하면서 누적합을 유지하면, 각 노드를 방문하는 시점의 누적합이 곧 '현재 노드보다 크거나 같은 모든 키의 합'이 됩니다.

알고리즘 단계

revInorder() 함수를 정의합니다. 이 함수는 트리의 루트 노드와 참조로 전달되는 누적합 변수 s를 매개변수로 받습니다.
루트가 null이면 그대로 반환합니다.
먼저 오른쪽 서브트리에 대해 revInorder(root->right, s)를 재귀 호출합니다.
s에 현재 노드의 값을 더하고(s := s + root->val), 그 값을 현재 노드에 저장합니다(root->val := s).
마지막으로 왼쪽 서브트리에 대해 revInorder(root->left, s)를 재귀 호출합니다.

메인 메서드인 convertBST()에서는 다음과 같이 처리합니다.

루트가 null이면 null을 반환합니다.
누적합 sum을 0으로 초기화합니다.
revInorder(root, sum)을 호출합니다.
root를 반환합니다.

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:
    void revInorder(TreeNode *root,int &s){
        if (root == NULL || root->val == 0)
            return;
        revInorder(root->right, s);
        s += root->val;
        root->val = s;
        revInorder(root->left, s);
    }
    TreeNode* convertBST(TreeNode* root){
        if (root == NULL || root->val == 0)
            return NULL;
        int sum = 0;
        revInorder(root, sum);
        return root;
    }
};
main(){
    Solution ob;
    vector<int> v = {5,2,8,NULL,NULL,6,9};
    TreeNode *root = make_tree(v);
    tree_level_trav(ob.convertBST(root));
}

입력

{5,2,8,NULL,NULL,6,9}

출력

[28, 30, 17, null, null, 23, 9]

복잡도 분석

시간 복잡도: O(n) — 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이(h)에 비례하며, 편향된 트리의 경우 최악 O(n)까지 증가할 수 있습니다.