C++で1と0の数が等しい最大の部分木を求めるアルゴリズム

問題の概要

0と1のみで構成された二分木が与えられます。この課題は、1と0の数が等しい最大の部分木を見つけることです。

解決のためのアプローチ

このアプローチでは、値が0であるすべてのノードを-1に置き換えます。こうすることで、「合計が0に等しい最大の部分木を見つける」という問題に帰着でき、プログラムが大幅にシンプルになります。

実装例

上記アプローチのC++コード

 #include <iostream>
using namespace std;
int maxi = -1;
struct node { // ツリーノードの構造体
    int data;
    struct node *right, *left;
};
struct node* newnode(int key){// 新しいノードを作成する
    struct node* temp = new node;
    temp->data = key;
    temp->right = NULL;
    temp->left = NULL;
    return temp;
}
void inorder(struct node* root){ // ツリーを走査する(未使用)
    if (root == NULL)
        return;
    inorder(root->left);
    cout << root->data << endl;
    inorder(root->right);
}
// 0と1の数が等しい部分木の最大サイズを返す関数
int calculatingmax(struct node* root){
    int a = 0, b = 0;
    if (root == NULL)
        return 0;
    a = calculatingmax(root->right); // 右の部分木
    a = a + 1; // 親ノードを含める
    b = calculatingmax(root->left); // 左の部分木
    a = b + a; // 現在の部分木のノード数
    if (root->data == 0) // 部分木全体の合計が0の場合
        // 合計サイズが現在の最大値を超える場合
        if (a >= maxi)
            maxi = a;
    return a;
}
int calc_sum(struct node* root){ // 各ノードの値を更新する
    if (root != NULL){
        if (root->data == 0){     
            root->data = -1;
        }
    }
    int a = 0, b = 0;
    // 左の子が存在する場合
    if (root->left != NULL)
        a = calc_sum(root->left);
    // 右の子が存在する場合
    if (root->right != NULL)
        b = calc_sum(root->right);
    root->data += (a + b);
    return root->data;
}
// ドライバーコード
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;
}

出力

6

コードの解説

上記のアプローチでは、まず値が0のノードをすべて-1に更新します。これにより、問題は「合計が0に等しい最大の部分木を見つける」という問題に帰着されます。この更新処理の過程で、各ノードにはそのノードを根とする部分木全体の合計値も同時に格納されます。次に、2つ目の関数を使って各ノードの値が0であるかを確認し、条件を満たす部分木に含まれるノード数の最大値を求めます。

この手法の計算量は、各ノードを2回訪問するだけなのでO(n)となり、非常に効率的です。また、再帰を用いた深さ優先探索の良い実践例とも言えます。

まとめ

このチュートリアルでは、1と0の数が等しい最大の部分木を見つける問題を解決しました。この問題に対するC++プログラムと、問題を解くための完全なアプローチ(標準的な方法)についても学びました。同じプログラムは、C、Java、Pythonなどの他のプログラミング言語でも記述できます。このチュートリアルが皆さんのお役に立てば幸いです。