ধরুন আমাদের একটি বাইনারি গাছ আছে। আমাদের কাজ হল প্রদত্ত গাছে একক মূল্যবান সাবট্রি গণনা করা। একটি একক মূল্যবান সাবট্রি হল একটি সাবট্রি, যেখানে সেই গাছের সমস্ত নোড একই মান ধারণ করে। ধরুন একটি গাছ নিচের মত -
চারটি একক মান সাবট্রি আছে। এগুলো নিচের মত -
আমরা বটম আপ পদ্ধতি ব্যবহার করে এটি সমাধান করতে পারি। ভিজিট করা প্রতিটি সাবট্রির জন্য, ট্রু রিটার্ন করুন, যদি এর নিচে রুট করা সাবট্রির মূল্য একক হয়, এবং কাউন্টারটি 1 দ্বারা বৃদ্ধি করুন। এখানে গণনা হল রিকারসিভ কলের জন্য রেফারেন্স প্যারামিটার। এবং বাম এবং ডান সাবট্রি একক মূল্যবান কিনা তা খুঁজে বের করতে ফেরত দেওয়া মান ব্যবহার করুন।
উদাহরণ
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* left, *right;
};
Node* getNode(int data) {
Node* newNode = new Node;
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
bool countSingleValuedSubtree(Node* root, int &count) {
if (root == NULL)
return true;
bool left = countSingleValuedSubtree(root->left, count);
bool right = countSingleValuedSubtree(root->right, count);
if (left == false || right == false)
return false;
if (root->left && root->data != root->left->data)
return false;
if (root->right && root->data != root->right->data)
return false;
count++;
return true;
}
int countSingleValSubtree(Node* root) {
int count = 0;
countSingleValuedSubtree(root, count);
return count;
}
int main() {
Node* root = getNode(5);
root->left = getNode(1);
root->right = getNode(5);
root->left->left = getNode(5);
root->left->right = getNode(5);
root->right->right = getNode(5);
cout << "Count of Single Valued Subtrees is: " << countSingleValSubtree(root);
} আউটপুট
Count of Single Valued Subtrees is: 4
