C++에서 임의의 이진 트리를 자식 합 속성을 만족하는 트리로 변환하는 방법

이번 튜토리얼에서는 임의의 이진 트리를 자식 합 속성(children sum property)을 만족하는 이진 트리로 변환하는 프로그램을 C++로 구현해 보겠습니다.

자식 합 속성이란?

자식 합 속성이란 각 노드의 값이 왼쪽 자식과 오른쪽 자식의 값의 합과 같아야 한다는 규칙입니다. 즉, 모든 내부 노드에 대해 다음 조건이 성립해야 합니다.

노드 값 = 왼쪽 자식 값 + 오른쪽 자식 값

단, 이 문제에는 중요한 제약 조건이 있습니다.

노드의 값은 증가만 할 수 있습니다.
트리의 구조는 변경할 수 없습니다.
기존 값을 감소시킬 수 없습니다.

접근 방법

변환은 재귀적으로 수행됩니다. 먼저 왼쪽과 오른쪽 서브트리를 각각 변환한 후, 부모 노드와 자식 노드들의 값 차이(diff)를 계산합니다.

자식들의 합이 부모 노드보다 크면, 부모 노드의 값을 자식들의 합만큼 증가시킵니다.
자식들의 합이 부모 노드보다 작으면, 자식 쪽으로 차이만큼 값을 증가시켜 전파합니다. 이때 왼쪽 자식이 있으면 왼쪽으로, 없으면 오른쪽으로 재귀적으로 증가시킵니다.

C++ 구현 예제

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

// 이진 트리 노드 구조체
class node {
public:
    int data;
    node* left;
    node* right;
    // 새 노드 생성
    node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};

// 자식 노드 값 증가 함수
void increment(node* node, int diff);

// 트리를 변환하는 메인 함수
void convert_Btree(node* node) {
    int left_data = 0, right_data = 0, diff;
    // 루트가 NULL이거나 리프 노드인 경우 종료
    if (node == NULL || (node->left == NULL &&
        node->right == NULL))
        return;
    else {
        // 왼쪽, 오른쪽 서브트리를 먼저 변환
        convert_Btree(node->left);
        convert_Btree(node->right);
        if (node->left != NULL)
            left_data = node->left->data;
        if (node->right != NULL)
            right_data = node->right->data;
        // 자식들의 합 계산
        diff = left_data + right_data - node->data;
        // 자식들의 합이 부모보다 큰 경우
        if (diff > 0)
            node->data = node->data + diff;
        if (diff < 0)
            increment(node, -diff);
    }
}

// 노드 값 증가 함수
void increment(node* node, int diff) {
    if (node->left != NULL) {
        node->left->data = node->left->data + diff;
        // 왼쪽으로 재귀적으로 이동
        increment(node->left, diff);
    }
    else if (node->right != NULL) {
        node->right->data = node->right->data + diff;
        increment(node->right, diff);
    }
}

// 중위 순회 출력
void printInorder(node* node) {
    if (node == NULL)
        return;
    printInorder(node->left);
    cout << node->data << " ";
    printInorder(node->right);
}

int main() {
    node *root = new node(50);
    root->left = new node(7);
    root->right = new node(2);
    root->left->left = new node(3);
    root->left->right = new node(5);
    root->right->left = new node(1);
    root->right->right = new node(30);

    cout << "변환 전: " << endl;
    printInorder(root);

    convert_Btree(root);

    cout << "\n변환 후: " << endl;
    printInorder(root);
    return 0;
}

실행 결과

변환 전:
3 7 5 50 1 2 30
변환 후:
14 19 5 50 1 31 30

동작 원리 설명

예제에서 루트 노드는 50이고, 자식들은 7과 2입니다. 자식들의 합(9)이 부모(50)보다 작으므로, 차이(41)만큼 자식 쪽으로 값이 전파되어 증가됩니다. 반대로 자식들의 합이 부모보다 큰 경우에는 부모 노드의 값을 증가시켜 속성을 만족하게 됩니다.

이 알고리즘의 시간 복잡도는 O(n²)입니다. 최악의 경우(편향된 트리) increment 함수가 여러 번 호출되며 각 호출이 트리의 깊이만큼 순회할 수 있기 때문입니다. 공간 복잡도는 재귀 호출 스택으로 인해 O(n)입니다.