นับ Single Valued Subtrees ใน Binary Tree ใน C++

สมมติมี Binary Tree ต้องการนับ Single Valued Subtrees Single Valued Subtree คือ Subtree ที่ทุก Node มีค่าเหมือนกัน ตัวอย่าง Tree:

มี Single Valued Subtrees 4 ต้น:

แก้ด้วย Bottom-up Manner: สำหรับ Subtree ที่ Visit คืนค่า true ถ้า Subtree Rooted ที่ Node นั้นเป็น Single Valued และเพิ่ม Counter Reference Parameter สำหรับ Recursive Call

ตัวอย่างโค้ด C++

#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