C++ 最大的子树，1 和 0 的个数相等

给定一个二叉树。现在我们的任务是找到具有相同数量 1 和 0 的最大子树；树只包含 0 和 1。

寻找解决方案的方法

在这种方法中，我们将用 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 的最大子树，同时在此更新中，我们还更新所有节点的值为以该节点为根的子树的重要性，现在我们使用第二个函数来计算和检查每个值为 0 的节点，然后找到该树中存在的最大节点数。

结论

在本教程中，我们解决了一个问题，以找到具有相等数量的 1 和 0 的最大子树。我们还学习了针对此问题的 C++ 程序以及解决此问题的完整方法(Normal)。我们可以用其他语言编写相同的程序，例如 C、java、python 和其他语言。我们希望本教程对您有所帮助。