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和其他语言。我们希望本教程对您有所帮助。