Hai tổng BST trong C++

Cho hai BST, kiểm tra có tồn tại nút trong cây 1 và nút trong cây 2 mà tổng = target hay không.

Ví dụ: 2 cây, target = 5 → Kết quả: true.

Giải thuật (Duyệt cây + Hash Set)

1. Map s lưu giá trị nút đã gặp và số hiệu cây (1 hoặc 2).
2. Hàm check(node, target, nodeNumber):
3. Nếu node null, trả về false.
4. curr = node->val, req = target - curr.
5. Nếu req có trong s và s[req] != nodeNumber → true.
6. s[curr] = nodeNumber.
7. Đệ quy trái/phải.
8. Main: gọi check(root1, target, 1), rồi check(root2, target, 2).

Ví dụ C++

#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) {
            if(val != NULL) temp->left = new TreeNode(val);
            else temp->left = new TreeNode(0); return;
        } else q.push(temp->left);
        if(!temp->right) {
            if(val != NULL) temp->right = new TreeNode(val);
            else temp->right = 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 {
public:
    map<int,int> s;
    bool check(TreeNode* node, int target, int nodeNumber) {
        if(!node) return false;
        int curr = node->val, req = target - curr;
        if(s.find(req) != s.end() && s[req] != nodeNumber) return true;
        s[curr] = nodeNumber;
        return check(node->left, target, nodeNumber) || check(node->right, target, nodeNumber);
    }
    bool twoSumBSTs(TreeNode* root1, TreeNode* root2, int target) {
        bool flag = check(root1, target, 1);
        return check(root2, target, 2);
    }
};

int main() {
    vector<int> v1 = {2,1,4}, v2 = {1,0,3};
    TreeNode *r1 = make_tree(v1), *r2 = make_tree(v2);
    Solution ob;
    cout << ob.twoSumBSTs(r1, r2, 5);
    return 0;
}

Đầu vào

[2,1,4] [1,0,3] 5

Đầu ra

1