ধরুন আমাদের একটি বাইনারি ট্রি আছে। আমাদের টাস্ক হলো দেয়া ট্রিতে সিংগেল ভ্যালুড সাবট্রির সংখ্যা গণনা করা। সিংগেল ভ্যালুড সাবট্রি হলো এমন একটি সাবট্রি যেখানে সকল নোড একই মান ধারণ করে। ধরুন একটি ট্রি নিচের মত:
এখানে চারটি সিংগেল ভ্যালুড সাবট্রি আছে। সেগুলো নিচের মত:
এটি বটম-আপ পদ্ধতিতে সমাধান করা যায়। প্রতিটি সাবট্রি ভিজিট করার সময়, যদি সাবট্রিটি সিংগেল ভ্যালুড হয়, তবে true রিটার্ন করুন এবং কাউন্টার ১ বাড়ান। এখানে কাউন্ট রেফারেন্স প্যারামিটার রিকার্সিভ কলের জন্য। এবং রিটার্ন করা ভ্যালু ব্যবহার করে বাম ও ডান সাবট্রি সিংগেল ভ্যালুড কিনা তা বের করুন।
উদাহরণ
#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
