Cho một cây nhị phân. Bây giờ chúng ta có nhiệm vụ tìm cây con lớn nhất có số lượng bằng nhau của 1 và 0; cây chỉ chứa 0 và 1.
Phương pháp tiếp cận để tìm giải pháp
Trong cách tiếp cận này, chúng tôi sẽ thay thế tất cả các nút bằng các giá trị từ 0 đến -1. Làm điều này sẽ làm cho chương trình của chúng ta đơn giản hơn vì bây giờ chúng ta cần tìm cây con lớn nhất có tổng bằng 0.
Ví dụ
Mã C ++ cho phương pháp tiếp cận trên
#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;
} Đầu ra
6
Giải thích về Quy tắc trên
Trong cách tiếp cận ở trên, chúng tôi cập nhật tất cả các nút có giá trị từ 0 đến -1 sau đó bây giờ chúng tôi giảm vấn đề của chúng tôi thành tìm cây con lớn nhất có tổng bằng 0 ngay bây giờ trong khi cập nhật này, chúng tôi cũng cập nhật tất cả các nút có giá trị đầy tầm quan trọng của cây con bắt nguồn từ nút đó và bây giờ chúng tôi sử dụng hàm thứ hai để tính toán và kiểm tra mọi nút có giá trị 0 và sau đó tìm số nút tối đa có trong cây đó.
Kết luận
Trong hướng dẫn này, chúng tôi giải quyết một vấn đề để tìm cây con Lớn nhất có số 1 và 0 bằng nhau. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường) mà chúng tôi đã giải quyết vấn đề này. Chúng ta có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy hướng dẫn này hữu ích.