মনে করুন দুটি বাইনারি সার্চ ট্রি আছে, আমাদের `True` রিটার্ন করতে হবে যদি এবং কেবল যদি প্রথম ট্রিতে একটি নোড এবং দ্বিতীয় ট্রিতে একটি নোড থাকে যাতে এদুটির যোগফল একটি দেয়া পূর্ণসংখ্যা `target` হয়। যদি ট্রি নিচের মোতাবিক হয় -
এবং `target` = 5 হলে, ফলাফল হবে true।
এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -
- একটি ম্যাপ `s` সংজ্ঞায়িত করুন
- `check()` নামক একটি মেথড সংজ্ঞায়িত করুন, এটি `node`, `target` এবং `nodeNumber` নেবে, এটি নিচের মোতাবিক কাজ করবে -
- যদি `node` বৈধ না হয়, তবে `false` রিটার্ন করুন
- `curr := node`-এর মান, `req := target - curr`
- যদি `req` `s`-এ বিদ্যমান থাকে এবং `s[req]` `nodeNumber` নয়, তবে `true` রিটার্ন করুন
- `s[curr] := nodeNumber`
- `check(node`-এর বাম, `target`, `nodeNumber)` OR `check(node`-এর ডান, `target`, `nodeNumber)` রিটার্ন করুন
- মেইন মেথডে, আমরা সেট করব -
- `flag := check(root1, target, 1)`
- `check(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
