Two Sum IV - Đầu vào là BST trong C++

Mô tả bài toán

Cho cây tìm kiếm nhị phân (BST) và giá trị mục tiêu k. Kiểm tra có tồn tại 2 nút trong BST có tổng bằng k không.

Giải pháp (Duyệt inorder + Hai con trỏ)

• Duyệt inorder BST → mảng đã sắp xếp.
• Dùng 2 con trỏ đầu/cuối tìm cặp tổng = k (O(N)).

Ví dụ minh họa

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

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

void insert(TreeNode** root, int val) {
    queue<TreeNode*> q; q.push(*root);
    while (q.size()) {
        TreeNode* temp = q.front(); q.pop();
        if (!temp->left) { temp->left = val ? new TreeNode(val) : new TreeNode(0); return; }
        else q.push(temp->left);
        if (!temp->right) { temp->right = val ? new TreeNode(val) : new TreeNode(0); return; }
        else q.push(temp->right);
    }
}

TreeNode* make_tree(vector<int> v) {
    TreeNode* root = new TreeNode(v[0]);
    for (int i = 1; i < v.size(); i++) insert(&root, v[i]);
    return root;
}

class Solution {
    vector<int> v;
    void inorder(TreeNode* root) {
        if (!root || root->val == 0) return;
        inorder(root->left);
        v.push_back(root->val);
        inorder(root->right);
    }
    bool findnode(int k) {
        int i = 0, j = v.size() - 1;
        while (i < j) {
            int t = v[i] + v[j];
            if (t == k) return true;
            if (t < k) i++; else j--;
        }
        return false;
    }
public:
    bool findTarget(TreeNode* root, int k) {
        inorder(root);
        sort(v.begin(), v.end()); // inorder đã cho mảng sort, dòng này dư
        return findnode(k);
    }
};

int main() {
    Solution ob;
    vector<int> v = {5,3,6,2,4,0,7}; // NULL = 0
    TreeNode* root = make_tree(v);
    cout << ob.findTarget(root, 9);
    return 0;
}

Đầu vào

{5,3,6,2,4,NULL,7}, 9

Đầu ra

1