Đếm số cây con đơn giá trị (Single Valued Subtrees) trong C++

Cho cây nhị phân. Đếm số cây con mà tất cả nút trong cây con đó có cùng giá trị (single valued subtrees).

Ví dụ cây có 4 cây con đơn giá trị.

Giải pháp bottom-up: đệ quy trả về true nếu cây con gốc tại nút hiện tại là single-valued, tăng biến đếm. Kiểm tra nút con trái/phải có cùng giá trị với nút hiện tại.

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

Kết quả

Count of Single Valued Subtrees is: 4