ค้นหาคู่ของตัวเลขที่ผลรวมเท่ากับค่าเป้าหมายใน BST ที่สมดุลด้วย C++

สมมติว่าเรามีต้นไม้ค้นหาทวีคูณสมดุล (Balanced Binary Search Tree) และค่าเป้าหมาย (target sum) เราต้องเขียนเมธอดเพื่อตรวจสอบว่ามีคู่ของโหนดใดโหนดหนึ่งที่ผลรวมของค่าของมันเท่ากับค่าเป้าหมายหรือไม่ โดยที่ BST นี้เป็น immutable (ไม่สามารถแก้ไขได้)

ตัวอย่างเช่น หากอินพุตเป็นต้นไม้ดังภาพ:

เอาต์พุทจะเป็นคู่ (9 + 26 = 35)

ขั้นตอนการแก้ปัญหา

1. กำหนดสแต็กสองอัน: s1 สำหรับการเดินแบบ in-order (น้อยไปมาก) และ s2 สำหรับ reverse in-order (มากไปน้อย)
2. ใช้ตัวแปรบูลีน done1, done2 ควบคุมการดึงค่าถัดไปจากแต่ละสแต็ก
3. ตัวแปร val1, val2 เก็บค่าที่ได้จากแต่ละการเดิน
4. เริ่มจากราก (curr1 = root, curr2 = root)
5. วนลูปไม่รู้จบ:
   • เดินหาค่าถัดไปที่น้อยที่สุด (in-order) ผ่าน s1 จนได้ val1
   • เดินหาค่าถัดไปที่มากที่สุด (reverse in-order) ผ่าน s2 จนได้ val2
   • ถ้า val1 != val2 และ val1 + val2 == target → พบคู่ ตอบ true
   • ถ้า val1 + val2 < target → ต้องเพิ่มค่า รีเซ็ต done1 = false เพื่อหาค่าถัดไปที่มากขึ้น
   • ถ้า val1 + val2 > target → ต้องลดค่า รีเซ็ต done2 = false เพื่อหาค่าถัดไปที่น้อยลง
   • ถ้า val1 >= val2 → ตัดกันแล้ว ไม่พบคู่ ตอบ false

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

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = NULL;
        right = NULL;
    }
};

bool isPairPresent(TreeNode* root, int target) {
    stack<TreeNode*> s1, s2;
    bool done1 = false, done2 = false;
    int val1 = 0, val2 = 0;
    TreeNode *curr1 = root, *curr2 = root;

    while (true) {
        // หาค่าถัดไปแบบ in-order (น้อยไปมาก)
        while (!done1) {
            if (curr1 != NULL) {
                s1.push(curr1);
                curr1 = curr1->left;
            } else {
                if (s1.empty()) done1 = true;
                else {
                    curr1 = s1.top(); s1.pop();
                    val1 = curr1->val;
                    curr1 = curr1->right;
                    done1 = true;
                }
            }
        }

        // หาค่าถัดไปแบบ reverse in-order (มากไปน้อย)
        while (!done2) {
            if (curr2 != NULL) {
                s2.push(curr2);
                curr2 = curr2->right;
            } else {
                if (s2.empty()) done2 = true;
                else {
                    curr2 = s2.top(); s2.pop();
                    val2 = curr2->val;
                    curr2 = curr2->left;
                    done2 = true;
                }
            }
        }

        if (val1 != val2 && val1 + val2 == target) {
            cout << "Pair Found: " << val1 << " + " << val2 << " = " << target << endl;
            return true;
        } else if (val1 + val2 < target) {
            done1 = false;
        } else if (val1 + val2 > target) {
            done2 = false;
        }

        if (val1 >= val2) return false;
    }
}

int main() {
    TreeNode* root = new TreeNode(16);
    root->left = new TreeNode(11);
    root->right = new TreeNode(21);
    root->left->left = new TreeNode(9);
    root->left->right = new TreeNode(13);
    root->right->left = new TreeNode(17);
    root->right->right = new TreeNode(26);
    int target = 35;
    cout << (isPairPresent(root, target));
}

อินพุต

TreeNode* root = new TreeNode(16);
root->left = new TreeNode(11);
root->right = new TreeNode(21);
root->left->left = new TreeNode(9);
root->left->right = new TreeNode(13);
root->right->left = new TreeNode(17);
root->right->right = new TreeNode(26);

เอาต์พุท

Pair Found: 9 + 26 = 35
1