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