Tìm một cặp có tổng cho trước trong BST C++

Tương tự bài 1003078398 nhưng chỉ cần tìm **một** cặp. Dùng cùng kỹ thuật two pointers trên BST (2 stack in-order ngược chiều). Khi tìm thấy cặp → in ra và dừng.

Ví dụ mã nguồn

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

struct Node {
    int data;
    Node *left, *right;
    Node(int d): data(d), left(nullptr), right(nullptr) {}
};

Node* insert(Node* root, int data) {
    if (!root) return new Node(data);
    if (data < root->data) root->left = insert(root->left, data);
    else if (data > root->data) root->right = insert(root->right, data);
    return root;
}

void findPair(Node* root, int target) {
    vector leftS, rightS;
    Node *curL = root, *curR = root;
    while (curL || curR || (!leftS.empty() && !rightS.empty())) {
        while (curL) { leftS.push_back(curL); curL = curL->left; }
        while (curR) { rightS.push_back(curR); curR = curR->right; }
        Node *l = leftS.back(), *r = rightS.back();
        int lv = l->data, rv = r->data;
        if (lv >= rv) break;
        if (lv + rv < target) { leftS.pop_back(); curL = l->right; }
        else if (lv + rv > target) { rightS.pop_back(); curR = r->left; }
        else {
            cout << lv << ' ' << rv << '\n';
            return;
        }
    }
}

int main() {
    Node* root = nullptr;
    root = insert(root, 25);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 15);
    root = insert(root, 21);
    root = insert(root, 19);
    root = insert(root, 31);
    findPair(root, 36); // 15 21
    return 0;
}

Kết quả

15 21