मान लीजिए हमारे पास एक बाइनरी ट्री है। हमारा कार्य दिए गए ट्री में एकल-मान वाले सबट्री की गिनती करना है। एक एकल-मान वाला सबट्री एक सबट्री है, जहां उस ट्री के सभी नोड्स समान मान रखते हैं। मान लीजिए एक ट्री नीचे जैसा है -
चार एकल-मान वाले सबट्री हैं। ये नीचे जैसे हैं -
हम इसे बॉटम-अप तरीके से हल कर सकते हैं। प्रत्येक विज़िट किए गए सबट्री के लिए, सत्य लौटाएं यदि उसके तहत रूटेड सबट्री एकल-मान वाला है, और काउंटर को 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
