資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 最大包含相同數量 1 和 0 的子樹
給定一棵二叉樹。現在我們的任務是找到包含相同數量的 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++ 程式以及解決此問題的完整方法（普通方法）。我們可以使用其他語言（如 C、Java、Python 和其他語言）編寫相同的程式。我們希望您覺得本教程有所幫助。
更新於： 2021 年 11 月 25 日
141 次檢視
廣告