ধরুন আমাদের একটি বাইনারি গাছ আছে। সেই গাছের নিয়ম নিম্নরূপ -
-
root.val ==0
-
যদি treeNode.val x হয় এবং treeNode.left শূন্য না হয়, তাহলে treeNode.left.val =2 * x + 1
-
যদি treeNode.val x হয় এবং treeNode.right শূন্য না হয়, তাহলে treeNode.right.val =2 * x + 2
এখন যেমন বাইনারি গাছ দূষিত। এটি নির্দেশ করে যে ট্রি নোডের সমস্ত ভ্যাল -1 এ পরিবর্তিত হয়েছে। আমাদের প্রথমে বাইনারি ট্রি পুনরুদ্ধার করতে হবে এবং তারপর নিচের মত FindElements ক্লাস বাস্তবায়ন করতে হবে -
-
FindElements(TreeNode* root) বস্তুটিকে একটি দূষিত বাইনারি ট্রি দিয়ে শুরু করে, আমাদের প্রথমে এটি পুনরুদ্ধার করতে হবে।
-
bool find(int target)। পুনরুদ্ধার করা বাইনারি ট্রিতে লক্ষ্য মান বিদ্যমান থাকলে এটি ফিরে আসবে।
তাই গাছটি যদি −
এর মত হয়
তাই পুনরুদ্ধারের পরে, আমরা যদি 1, 3 এবং 5 খুঁজে বের করার চেষ্টা করি, তাহলে ফলাফল সত্য, সত্য এবং মিথ্যা হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি সেট a
সংজ্ঞায়িত করুন -
একটি dfs() পদ্ধতি সংজ্ঞায়িত করুন, এটি রুট এবং রুটভাল গ্রহণ করবে। rootVal প্রাথমিকভাবে -1
-
রুট শূন্য হলে, ফেরত দিন
-
যদি রুটভাল -1 হয়, তাহলে রুটের মান 0 হিসাবে সেট করুন, অন্যথায় এটি রুটভাল হিসাবে সেট করুন
-
একটি
-এ রুটের মান সন্নিবেশ করান -
dfs (রুটের বামে, রুটের 2* মান + 1), dfs (রুটের ডানদিকে, রুটের 2* মান + 2)
-
আরম্ভ করার জন্য, (বা পুনর্গঠন), আমরা dfs(root, -1) কল করব
-
কিছু উপাদান খুঁজে পেতে, উপাদানটি সেখানে থাকবে কিনা তা পরীক্ষা করে দেখুন, যদি তা সত্য হয়, অন্যথায় মিথ্যা হয়।
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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 FindElements {
public:
set <int> a;
void dfs(TreeNode* root,int rootVal=-1){
if(!root)return;
root->val = rootVal == -1?0:rootVal;
a.insert(root->val);
dfs(root->left,2*root->val + 1);
dfs(root->right, 2*root->val + 2);
}
FindElements(TreeNode* root) {
dfs(root);
}
bool find(int t) {
return a.find(t)!=a.end();
}
};
main(){
vector<int> v = {-1,-1,-1,-1,-1};
TreeNode *root = make_tree(v);
FindElements ob(root);
cout << (ob.find(1)) << endl;
cout << (ob.find(3)) << endl;
cout << (ob.find(5)) << endl;
} ইনপুট
Initialize the tree with [-1,-1,-1,-1,-1], then call find(1), find(3) and find(5)
আউটপুট
1 1 0
