C++ 最大子树，1 和 0 的数量相等
c++server side programmingprogramming
给定一个二叉树。现在我们的任务是找到 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 computingmax(struct node* root){
int a = 0, b = 0;
if (root == NULL)
return 0;
a = computingmax(root->right); // 右子树
a = a + 1; // 包括父节点
b = computingmax(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++ 程序以及我们解决这个问题的完整方法(正常)。我们可以用其他语言(如 C、java、python 和其他语言)编写相同的程序。我们希望您觉得本教程有用。
