একটি বাইনারি সার্চ ট্রি (BST) এবং একটি টার্গেট মান দেওয়া আছে। চেক করতে হবে BST-এ এমন দুটি উপাদান আছে কিনা যাদের যোগফল টার্গেটের সমান।
ইনপুট ট্রি (চিত্রে) এবং টার্গেট ৯ হলে আউটপুট True।
সমাধানের ধাপসমূহ
- v অ্যারে সংজ্ঞায়িত করুন
- inorder() ফাংশন: BST-র ইনঅর্ডার ট্রাভার্সাল করে v-এ মান সংরক্ষণ করুন
- findnode() ফাংশন: টু-পয়েন্টার টেকনিক দিয়ে v-এ টার্গেট যোগফল খুঁজুন
- মূল ফাংশন: inorder(root), sort(v), findnode(k) রিটার্ন করুন
উদাহরণ
#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; ival == 0) return;
inorder(root->left);
v.push_back(root->val);
inorder(root->right);
}
bool findnode(int k){
int n = v.size(), i = 0, j = n - 1;
while (i < j) {
int t = v[i] + v[j];
if (t == k) return true;
if (t < k) i++;
else j--;
}
return false;
}
bool findTarget(TreeNode* root, int k){
inorder(root);
sort(v.begin(), v.end());
return findnode(k);
}
};
int main(){
Solution ob;
vector<int> v = {5,3,6,2,4,NULL,7};
TreeNode *root = make_tree(v);
cout << (ob.findTarget(root, 9));
} ইনপুট
{5,3,6,2,4,NULL,7},9আউটপুট
1
