1と0の数が等しいC++最大のサブツリー

二分木が与えられます。ここで、1と0の数が等しい最大のサブツリーを見つける必要があります。ツリーには0と1のみが含まれます。

解決策を見つけるためのアプローチ

このアプローチでは、すべてのノードを0から-1の値に置き換えます。これを行うと、合計が0に等しい最大のサブツリーを見つける必要があるため、プログラムが簡単になります。

例

上記のアプローチの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;
}

出力

6

上記のコードの説明

上記のアプローチでは、値が0から-1のすべてのノードを更新してから、問題を減らして、合計が0に等しい最大のサブツリーを見つけます。この更新中に、すべてのノードをfullの値で更新します。そのノードをルートとするサブツリーの重要性。次に、2番目の関数を使用して、値が0のすべてのノードを計算およびチェックし、そのツリーに存在するノードの最大数を見つけます。

結論

このチュートリアルでは、問題を解決して、1と0の数が等しい最大のサブツリーを見つけます。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（通常）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。