C++로 서로 바뀐 두 노드를 찾아 이진 탐색 트리(BST) 복구하기

문제 소개

이진 탐색 트리(Binary Search Tree, BST)가 하나 있다고 가정해 보겠습니다. 어떤 이유로 이 트리의 두 노드 값이 서로 교환되어 BST의 성질이 깨졌다면, 트리의 구조는 그대로 유지한 채 두 값을 다시 되돌려 올바른 이진 탐색 트리로 복구해야 합니다.

예를 들어 아래 왼쪽과 같은 트리가 주어지면, 복구된 트리는 오른쪽과 같습니다.

해결 접근 방식

이 문제의 핵심은 중위 순회(inorder traversal)입니다. 올바른 BST를 중위 순회하면 항상 오름차순으로 정렬된 값이 얻어집니다. 따라서 두 노드가 서로 바뀌어 있다면 중위 순회 과정에서 반드시 '직전 값이 현재 값보다 큰' 지점, 즉 순서가 어긋난 구간이 나타납니다. 이 위반 지점들을 추적하면 교환된 두 노드를 정확히 찾아낼 수 있습니다.

구체적인 알고리즘은 다음과 같습니다.

직전에 방문한 노드를 가리키는 prev, 순서 위반의 첫 번째 노드를 저장할 first, 두 번째 노드를 저장할 second 포인터를 준비합니다.
노드를 인자로 받는 findProblem() 메서드를 정의합니다.
노드가 null이면 즉시 반환합니다.
현재 노드의 왼쪽 서브트리에 대해 findProblem()을 재귀 호출합니다.
prev가 null이 아니고 prev->val > node->val이라면 순서 위반이 발생한 것입니다. 이때 first가 아직 비어 있으면 first = prev로 설정하고, second = node로 갱신합니다.
prev = node로 직전 노드를 갱신합니다.
오른쪽 서브트리에 대해 findProblem()을 재귀 호출합니다.
메인 메서드에서는 prev, first, second를 null로 초기화한 뒤 findProblem(root)을 호출하고, 마지막으로 first와 second 노드의 값을 서로 교환하면 트리가 복구됩니다.

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->val == 0){
                cout << "null" << ", ";
            }else{
                cout << curr->val << ", ";
            }
        }
    }
    cout << "]" << endl;
}
class Solution {
    public:
    TreeNode* prev;
    TreeNode* first;
    TreeNode* second;
    void swapValue(TreeNode* first, TreeNode* second){
        int x = first->val;
        first->val = second->val;
        second->val = x;
    }
    void findProblem(TreeNode* node){
        if(!node || node->val == 0) return;
        findProblem(node->left);
        if(prev != NULL && prev->val != 0 && prev->val > node->val){
            if(!first){
                first = prev;
            }
            second = node;
        }
        prev = node;
        findProblem(node->right);
    }
    void recoverTree(TreeNode* root) {
        prev = first = second = NULL;
        findProblem(root);
        swapValue(first, second);
    }
};
int main(){
    vector<int> v = {1,3,NULL,NULL,2};
    TreeNode *root = make_tree(v);
    Solution ob;
    ob.recoverTree(root);
    tree_level_trav(root);
    return 0;
}

입력

{1,3,NULL,NULL,2}

출력

[3, 1, null, null, 2]

복잡도 분석

시간 복잡도: O(n) — 트리의 모든 노드를 정확히 한 번씩 방문합니다.
공간 복잡도: O(h) — 재귀 호출 스택의 깊이는 트리의 높이 h에 비례하며, 균형 잡힌 트리라면 O(log n)입니다.