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인 가장 큰 하위 트리를 찾는 문제로 축소했습니다. 해당 노드에 뿌리를 둔 하위 트리의 중요성과 이제 두 번째 함수를 사용하여 값이 0인 모든 노드를 계산하고 확인한 다음 해당 트리에 있는 최대 노드 수를 찾습니다.

결론

이 튜토리얼에서는 1과 0이 같은 가장 큰 하위 트리를 찾는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.