Đếm cây con có tổng trọng số bằng x trong C++

Cho cây nhị phân và giá trị x, đếm số cây con có tổng trọng số nút bằng x.

Ý tưởng

• Đệ quy bottom-up: tính tổng cây con trái, cây con phải, cộng trọng số gốc.
• Nếu tổng == x thì tăng đếm.
• Dùng biến static để lưu gốc ban đầu và đếm.

Ví dụ hoàn chỉnh

#include <bits/stdc++.h>
using namespace std;

struct Tree_Node {
    int data;
    Tree_Node *Left, *Right;
};

Tree_Node* insert_Node(int data) {
    Tree_Node* new_node = (Tree_Node*)malloc(sizeof(Tree_Node));
    new_node->data = data;
    new_node->Left = new_node->Right = NULL;
    return new_node;
}

int subtrees_x(Tree_Node* root, int x) {
    static int count = 0;
    static Tree_Node* temp = root;
    int Left_subtree = 0, Right_subtree = 0;
    if (root == NULL)
        return 0;
    Left_subtree += subtrees_x(root->Left, x);
    Right_subtree += subtrees_x(root->Right, x);
    int sum = Left_subtree + Right_subtree + root->data;
    if (sum == x)
        count++;
    if (temp != root) {
        int set = Left_subtree + root->data + Right_subtree;
        return set;
    }
    return count;
}

int main() {
    Tree_Node* root = insert_Node(10);
    root->Left = insert_Node(20);
    root->Right = insert_Node(12);
    root->Left->Left = insert_Node(14);
    root->Left->Right = insert_Node(1);
    root->Right->Left = insert_Node(21);
    root->Right->Right = insert_Node(11);
    int x = 14;
    cout << "Số cây con có tổng " << x << ": " << subtrees_x(root, x);
    return 0;
}

Kết quả

Số cây con có tổng 14: 1