นับคู่โหนดใน Binary Tree ที่ผลรวมเท่ากับ x ใน C++

โจทย์: ให้ Binary Tree และค่า x ต้องการนับจำนวนคู่โหนด (unordered pair) ที่ผลรวมของค่าเท่ากับ x

แนวคิด: Brute Force ด้วยการตรวจสอบทุกคู่

สำหรับแต่ละโหนด ptr ตรวจสอบว่ามีโหนดอื่นในต้นไม้ที่มีค่าเท่ากับ x - ptr->data หรือไม่

ฟังก์ชันตรวจสอบ

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;
    return check(root->left, ptr, x) || check(root->right, ptr, x);
}

ฟังก์ชันนับคู่

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

หมายเหตุ: เนื่องจากแต่ละคู่ถูกนับ 2 ครั้ง (ครั้งหนึ่งจากโหนดแรก อีกครั้งจากโหนดที่สอง) จึงต้องหาร 2 ท้ายสุด

ตัวอย่างเต็ม

#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;
    return check(root->left, ptr, x) || check(root->right, ptr, x);
}

void total_pairs(tree_node* root, tree_node* ptr, int x, int& total) {
    if (ptr == NULL) return;
    if (check(root, ptr, x)) 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;  // หาร 2 เพราะนับซ้ำ
    
    cout << "Count of pairs: " << total;
    return 0;
}

ผลลัพธ์

Count of pairs in a binary tree whose sum is equal to a given value x are: 2

คู่ที่ได้: (2,3) และ (1,4)

การปรับปรุงประสิทธิภาพ

สามารถใช้ Hash Set เก็บค่าที่ผ่านมาแล้ว ทำให้เป็น O(n) แทน O(n²)