C++ में सिंगल वैल्यूड सबट्री की संख्या ज्ञात करें

मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हमारा कार्य दिए गए पेड़ में एकल मूल्यवान उपप्रकारों को गिनना है। एक एकल मूल्यवान सबट्री एक सबट्री है, जहां उस पेड़ के सभी नोड्स में समान मान होता है। मान लीजिए एक पेड़ नीचे जैसा है -

चार सिंगल वैल्यू सबट्री हैं। ये नीचे की तरह हैं -

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