ধরুন আমাদের দুটি বাইনারি সার্চ ট্রি আছে, আমাদের ট্রু রিটার্ন করতে হবে যদি প্রথম ট্রিতে একটি নোড থাকে এবং দ্বিতীয় ট্রিতে একটি নোড থাকে এবং এই নোডগুলির যোগফল একটি প্রদত্ত পূর্ণসংখ্যা লক্ষ্য। . তাই গাছটি যদি −
এর মত হয়
এবং লক্ষ্য 5, তাহলে ফলাফলটি সত্য।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি মানচিত্র সংজ্ঞায়িত করুন
- চেক() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি নোড, লক্ষ্য এবং নোড নম্বর নেবে, এটি নিম্নরূপ কাজ করবে -
- নোড বৈধ হলে মিথ্যা ফেরত দিন
- curr :=নোডের মান, req :=লক্ষ্য – curr
- যদি s-এ req থাকে এবং s[req] nodeNumber না হয়, তাহলে true ফেরত দিন
- s[curr] :=nodeNumber
- রিটার্ন চেক (নোডের বামে, লক্ষ্য, নোড নম্বর) বা চেক (নোডের ডানদিকে, লক্ষ্য, নোড নম্বর)
- মূল পদ্ধতিতে, আমরা − সেট করব
- পতাকা :=চেক(root1, target, 1)
- রিটার্ন চেক(root2, target, 2)
উদাহরণ(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;
}
};
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;
int 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);
}
};
main(){
vector<int> v1 = {2,1,4};
vector<int> v2 = {1,0,3};
TreeNode *r1 = make_tree(v1);
TreeNode *r2 = make_tree(v2);
Solution ob;
cout <<ob.twoSumBSTs(r1, r2, 5);
} ইনপুট
[2,1,4] [1,0,3] 5
আউটপুট
1
