C++で単一値のサブツリーの数を検索する

二分木があるとします。私たちのタスクは、指定されたツリー内の単一値のサブツリーをカウントすることです。単一値のサブツリーはサブツリーであり、そのツリーのすべてのノードに同じ値が含まれています。木が以下のようなものだとしましょう-

4つの単一値サブツリーがあります。これらは以下のようなものです-

これはボトムアップ方式で解決できます。訪問したすべてのサブツリーについて、その下にルートされたサブツリーが単一値の場合はtrueを返し、カウンターを1増やします。ここで、countは再帰呼び出しの参照パラメーターです。そして、戻り値を使用して、左右のサブツリーが単一値であるかどうかを確認します。

例

#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