Đếm cặp nút từ hai BST có tổng bằng x trong C++

Cho hai cây tìm kiếm nhị phân (BST) và số x. Tìm số cặp nút (một từ BST1, một từ BST2) có tổng giá trị bằng x.

Ví dụ

Đầu vào − Hai BST như hình minh họa.

Đầu ra − 1

Giải thích − Cặp (8, 6).

Đầu vào − Hai BST khác.

Đầu ra − 2

Giải thích − Các cặp: (5,15) và (4,16).

Phương pháp giải

Duyệt BST1 theo inorder (tăng dần) và BST2 theo inorder ngược (giảm dần) bằng stack. So sánh tổng hai nút đỉnh stack với x:

• Nếu tổng == x: count++, pop cả hai, đi phải BST1 và trái BST2.
• Nếu tổng < x: pop BST1, đi phải BST1.
• Nếu tổng > x: pop BST2, đi trái BST2.

Ví dụ code

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

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

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

int BST_sum_x(Tree* BST_1, Tree* BST_2, int x) {
    int count = 0;
    Tree *stack_top_1, *stack_top_2;
    stack stack_1, stack_2;
    if (!BST_1 || !BST_2) return 0;
    while (true) {
        while (BST_1) { stack_1.push(BST_1); BST_1 = BST_1->left; }
        while (BST_2) { stack_2.push(BST_2); BST_2 = BST_2->right; }
        if (stack_1.empty() || stack_2.empty()) break;
        stack_top_1 = stack_1.top();
        stack_top_2 = stack_2.top();
        int sum = stack_top_1->data + stack_top_2->data;
        if (sum == x) {
            count++;
            stack_1.pop(); stack_2.pop();
            BST_1 = stack_top_1->right;
            BST_2 = stack_top_2->left;
        } else if (sum < x) {
            stack_1.pop();
            BST_1 = stack_top_1->right;
        } else {
            stack_2.pop();
            BST_2 = stack_top_2->left;
        }
    }
    return count;
}

int main() {
    Tree* BST_1 = insert_node(15);
    BST_1->left = insert_node(10);
    BST_1->right = insert_node(8);
    BST_1->left->left = insert_node(12);
    BST_1->left->right = insert_node(24);
    BST_1->right->left = insert_node(16);
    Tree* BST_2 = insert_node(20);
    BST_2->left = insert_node(16);
    BST_2->right = insert_node(4);
    BST_2->left->left = insert_node(18);
    BST_2->left->right = insert_node(28);
    BST_2->right->left = insert_node(22);
    int x = 28;
    cout << "Count of pairs from two BSTs whose sum is equal to a given value x are: " << BST_sum_x(BST_1, BST_2, x);
    return 0;
}

Đầu ra

Count of pairs from two BSTs whose sum is equal to a given value x are: 1