Tìm số lượng cây con có giá trị duy nhất trong C ++

Giả sử chúng ta có một cây nhị phân. Nhiệm vụ của chúng ta là đếm các cây con có giá trị đơn lẻ trong cây đã cho. Một cây con có giá trị duy nhất là một cây con, trong đó tất cả các nút của cây đó đều chứa cùng một giá trị. Giả sử một cái cây giống như bên dưới -

Có bốn cây con giá trị đơn. Những thứ này giống như bên dưới -

Chúng tôi có thể giải quyết vấn đề này bằng cách sử dụng từ dưới lên. Đối với mỗi cây con được truy cập, trả về true, nếu cây con, gốc bên dưới nó có giá trị duy nhất và tăng bộ đếm lên 1. Đây count là tham số tham chiếu cho lệnh gọi đệ quy. Và sử dụng giá trị trả về để tìm hiểu xem các cây con bên trái và bên phải có phải là giá trị đơn lẻ hay không.

Ví dụ

#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);
}

Đầu ra

Count of Single Valued Subtrees is: 4