นับคู่จากสอง BST ที่ผลรวมเท่ากับค่า x ที่กำหนดใน C++

เราได้รับต้นไม้ค้นหาทวีคูณ (BST) สองต้นเป็นอินพุตและตัวแปร x เป้าหมายคือหาคู่ของโหนดจากต้นไม้แต่ละต้นที่ผลรวมของค่าโหนดเท่ากับ x เลือกโหนด 1 จาก BST_1 และโหนด 2 จาก BST_2 บวกส่วนข้อมูลของทั้งสอง ถ้า sum=x เพิ่ม count

มาดูตัวอย่าง

อินพุต

เอาต์พุต − จำนวนคู่จากสอง BST ที่ผลรวมเท่ากับค่า x ที่กำหนด คือ 1

คำอธิบาย − คู่คือ (8,6)

อินพุต

เอาต์พุต − จำนวนคู่จากสอง BST ที่ผลรวมเท่ากับค่า x ที่กำหนด คือ 2

คำอธิบาย − คู่คือ (5,15) และ (4,16)

แนวทางที่ใช้ในโปรแกรม

ในแนวทางนี้เราจะเดินทาง BST ด้วยวิธี inorder แบบ iterative เดินทาง BST 1 จากโหนดเล็กสุดไปใหญ่สุดด้วย inorder แบบ iterative และเดินทาง BST 2 จากกลับของ inorder iterative นำผลรวมของโหนดปัจจุบันของทั้งสอง BST มาบวกกัน ถ้า sum == x เพิ่ม count ถ้า sum>x ให้ไปยัง inorder predecessor ของโหนดปัจจุบันใน BST 2 ถ้า sum<x ให้ไปยัง inorder successor ของโหนดปัจจุบันใน BST 1

• รับต้นไม้สองต้น BST_1 และ BST_2 ที่มีส่วนข้อมูลเป็นจำนวนเต็มและพอยน์เตอร์ left, right ไปยังโหนดลูก
• ฟังก์ชัน insert_node(int data) แทรกโหนดใหม่เข้า Tree ด้วยข้อมูลและคืนพอยน์เตอร์ไปยังมัน
• สร้าง BST ทั้งสองด้วย insert_node() และส่งให้ BST_sum_x(Tree* BST_1, Tree* BST_2, int x)
• ฟังก์ชัน BST_sum_x(Tree* BST_1, Tree* BST_2, int x) รับรากของทั้งสองต้นไม้ คืนจำนวนคู่ของโหนดที่ผลรวมส่วนข้อมูลเป็น x
• กำหนด count เริ่มต้น 0 สำหรับจำนวนคู่ที่ผลรวมเป็น x
• สำหรับการเดินทาง inorder แบบ iterative ใช้ตัวแปร Tree* stack_top_1, *stack_top_2
• สร้างสองสแท็ก stack<Tree*> stack_1, stack_2
• เริ่มลูป while ภายนอก
• ไปยังโหนดซ้ายสุด (เล็กสุด) ของ BST_1 ด้วยลูป while และ push โหนดทั้งหมดเข้า stack_1
• ไปยังโหนดขวาสุด (ใหญ่สุด) ของ BST_2 ด้วยลูป while และ push โหนดทั้งหมดเข้า stack_2
• ถ้าสแท็กใดว่าง break ลูป while ภายนอก
• นำโหนดบนสุดของทั้งสองสแท็กมาบวกส่วนข้อมูลเก็บใน temp
• ถ้า temp (sum) == x เพิ่ม count นำโหนดบนสุดออกจากทั้ง stack_1 และ stack_2 ด้วย pop
• กำหนด BST_1=stack_1->right และ BST_2=stack_2->left ( successor ถัดไปใน BST_1 และ predecessor ใน BST_2 )
• ถ้า temp<x นำบนสุดออกจาก stack_1 เท่านั้น และไปยัง successor ถัดไปใน BST_1
• ถ้า temp>x นำบนสุดออกจาก stack_2 เท่านั้น และไปยัง predecessor ถัดไปใน BST_2
• ท้ายสุดของลูป while ภายนอก count มีจำนวนคู่ที่โหนดของทั้งสอง BST มีผลรวม x
• คืน count

ตัวอย่างโค้ด C++

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

int BST_sum_x(Tree* BST_1, Tree* BST_2, int x){
    int count = 0;
    Tree* stack_top_1, *stack_top_2;
    stack<Tree*> stack_1, stack_2;
    if (BST_1 == NULL || BST_2 == NULL){
        return 0;
    }
    while (1){
        while (BST_1 != NULL){
            stack_1.push(BST_1);
            BST_1 = BST_1->left;
        }
        while (BST_2 != NULL){
            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 temp = stack_top_1->data + stack_top_2->data;
        if (temp == x){
            count++;
            stack_1.pop();
            stack_2.pop();
            BST_1 = stack_top_1->right;
            BST_2 = stack_top_2->left;
        } else if (temp < x){
            stack_1.pop();
            BST_1 = stack_top_1->right;
        } else {
            stack_2.pop();
            BST_2 = stack_top_2->left;
        }
    }
    return count;
}

int main(){
    //BST 1
    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);
    //BST 2
    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 ar: "<<BST_sum_x(BST_1, BST_2, x);
    return 0;
}

เอาต์พุต

หากรันโค้ดด้านบนจะได้ผลลัพธ์ดังนี้ −

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