Đếm cặp nút trong cây nhị phân có tổng bằng x trong C++

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

Ý tưởng

• Hàm check(root, ptr, x) kiểm tra xem có nút nào trong cây có giá trị x - ptr->data không.
• Hàm total_pairs(root, ptr, x, total) duyệt qua từng nút ptr, gọi check để đếm.
• Kết quả chia 2 vì mỗi cặp được đếm hai lần.

Ví dụ hoàn chỉnh

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

struct tree_node {
    int data;
    tree_node *left, *right;
};

tree_node* create_node(int data) {
    tree_node* newNode = (tree_node*)malloc(sizeof(tree_node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

bool check(tree_node* root, tree_node* ptr, int x) {
    if (root == NULL)
        return false;
    if (root != ptr && (root->data + ptr->data) == x)
        return true;
    if (check(root->left, ptr, x) || check(root->right, ptr, x))
        return true;
    return false;
}

void total_pairs(tree_node* root, tree_node* ptr, int x, int& total) {
    if (ptr == NULL)
        return;
    if (check(root, ptr, x) == true)
        total++;
    total_pairs(root, ptr->left, x, total);
    total_pairs(root, ptr->right, x, total);
}

int main() {
    int x = 5;
    int total = 0;
    tree_node* root = create_node(5);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(1);
    root->left->right = create_node(4);
    root->right->left = create_node(6);
    total_pairs(root, root, x, total);
    total = total / 2;
    cout << "Số cặp có tổng " << x << ": " << total;
    return 0;
}

Kết quả

Số cặp có tổng 5: 2