C++로 구현하는 1과 0의 개수가 같은 가장 큰 서브트리 찾기

문제 소개

이진 트리가 하나 주어집니다. 트리에는 0과 1만 포함되어 있으며, 우리의 목표는 1과 0의 개수가 동일한 가장 큰 서브트리(하위 트리)를 찾는 것입니다.

해결 접근 방식

이 문제의 핵심 아이디어는 간단합니다. 먼저 값이 0인 모든 노드를 -1로 변환합니다. 그러면 문제가 "합이 0인 가장 큰 서브트리 찾기"로 단순화됩니다. 1과 -1의 합이 0이라는 것은 곧 원래 트리에서 1과 0의 개수가 같다는 의미이기 때문입니다.

알고리즘의 전체 흐름은 다음과 같습니다.

값 변환 및 합 계산(calc_sum): 트리를 후위 순회하며 값이 0인 노드를 -1로 바꾸고, 각 노드에 자신을 루트로 하는 서브트리 전체의 합을 저장합니다.
최대 크기 탐색(calculatingmax): 갱신된 트리를 순회하며 값이 0인 노드를 찾습니다. 값이 0이면 해당 서브트리에서 1과 0의 개수가 같다는 뜻이며, 이런 서브트리 중 노드 수가 가장 많은 것을 전역 변수 maxi에 기록합니다.

C++ 구현 코드

 #include <iostream>
using namespace std;
int maxi = -1;
struct node { // structure of our tree node
    int data;
    struct node *right, *left;
};
struct node* newnode(int key){// To create a new node
    struct node* temp = new node;
    temp->data = key;
    temp->right = NULL;
    temp->left = NULL;
    return temp;
}
void inorder(struct node* root){ // traversing the tree(not used)
    if (root == NULL)
        return;
    inorder(root->left);
    cout << root->data << endl;
    inorder(root->right);
}
// Function to return the maximum size of
// the sub-tree having an equal number of 0's and 1's
int calculatingmax(struct node* root){
    int a = 0, b = 0;
    if (root == NULL)
        return 0;
    a = calculatingmax(root->right); // right subtree
    a = a + 1; // including parent
    b = calculatingmax(root->left); // left subtree
    a = b + a; // number of nodes at current subtree
    if (root->data == 0) // if the sum of whole subtree is 0
        // If the total size exceeds
        // the current max
        if (a >= maxi)
            maxi = a;
    return a;
}
int calc_sum(struct node* root){ // updating the values at each node
    if (root != NULL){
        if (root->data == 0){        
            root->data = -1;
        }
    }
    int a = 0, b = 0;
    // If left child exists
    if (root->left != NULL)
        a = calc_sum(root->left);
    // If right child exists
    if (root->right != NULL)
        b = calc_sum(root->right);
    root->data += (a + b);
    return root->data;
}
// Driver code
int main(){
    struct node* root = newnode(1);
    root->right = newnode(0);
    root->right->right = newnode(1);
    root->right->right->right = newnode(1);
    root->left = newnode(0);
    root->left->left = newnode(1);
    root->left->left->left = newnode(1);
    root->left->right = newnode(0);
    root->left->right->left = newnode(1);
    root->left->right->left->left = newnode(1);
    root->left->right->right = newnode(0);
    root->left->right->right->left = newnode(0);
    root->left->right->right->left->left = newnode(1);
    calc_sum(root);
    calculatingmax(root);
    //  cout << "h";
    cout << maxi;
    return 0;
}

실행 결과

코드 상세 설명

위 코드의 동작을 단계별로 살펴보겠습니다.

1단계 — calc_sum 함수: 트리를 재귀적으로 순회하면서 값이 0인 노드를 -1로 변경합니다. 동시에 자식 서브트리들의 합을 부모 노드 값에 더해, 각 노드에는 "자신을 루트로 하는 서브트리 전체의 합"이 저장됩니다.

2단계 — calculatingmax 함수: 갱신된 트리를 다시 순회하며 현재 서브트리에 포함된 노드의 개수를 계산합니다. 만약 현재 노드의 값이 0이라면(즉, 서브트리의 총합이 0이라면) 1과 0의 개수가 같은 것이므로, 지금까지의 최댓값(maxi)과 비교하여 더 크면 값을 갱신합니다.

복잡도 분석: 트리를 두 번 순회하므로 시간 복잡도는 O(N)이며, N은 트리의 노드 수입니다. 공간 복잡도는 재귀 호출 스택으로 인해 최악의 경우(트리가 한쪽으로 치우친 경우) O(N)이 됩니다.

마무리

이번 글에서는 1과 0의 개수가 같은 가장 큰 서브트리를 찾는 문제를 다루었습니다. 0을 -1로 치환해 문제를 "합이 0인 서브트리 찾기"로 바꾸는 아이디어가 핵심이었으며, 덕분에 코드가 훨씬 단순해졌습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 튜토리얼이 여러분의 학습에 도움이 되었기를 바랍니다.