मान लीजिए हमारे पास एक बाइनरी ट्री है। उस ट्री के नियम इस प्रकार हैं:
root.val == 0
यदि treeNode.val x है और treeNode.left null नहीं है, तो treeNode.left.val = 2 * x + 1
यदि treeNode.val x है और treeNode.right null नहीं है, तो treeNode.right.val = 2 * x + 2
अब चूंकि बाइनरी ट्री दूषित है। यह इंगित करता है कि ट्री नोड के सभी मान -1 में बदल दिए गए हैं। हमें पहले बाइनरी ट्री को पुनर्प्राप्त करना होगा और फिर FindElements क्लास को इस प्रकार लागू करना होगा:
FindElements(TreeNode* root) दूषित बाइनरी ट्री के साथ ऑब्जेक्ट को प्रारंभ करता है, हमें पहले इसे पुनर्प्राप्त करना होगा।
bool find(int target)। यह लौटाएगा कि लक्ष्य मान पुनर्प्राप्त बाइनरी ट्री में मौजूद है या नहीं।
इसलिए यदि ट्री इस तरह है:
इसलिए पुनर्प्राप्त करने के बाद, यदि हम 1, 3 और 5 को खोजने का प्रयास करते हैं, तो परिणाम true, true और false होंगे।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
एक सेट a परिभाषित करें
एक dfs() विधि परिभाषित करें, यह root और rootVal लेगा। rootVal प्रारंभ में -1 है
यदि root null है, तो लौटें
यदि rootVal -1 है, तो root का मान 0 पर सेट करें, अन्यथा इसे rootVal पर सेट करें
root के मान को a में सम्मिलित करें
dfs(left of root, 2* root का मान + 1), dfs(right of root, 2* root का मान + 2) कॉल करें
प्रारंभिककरण (या पुनर्निर्माण) के लिए, हम dfs(root, -1) कॉल करेंगे
किसी तत्व को खोजने के लिए, जांचें कि तत्व a में होगा या नहीं, यदि हां तो true लौटाएं, अन्यथा false।
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#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();
}
};
int 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;
}
इनपुट
ट्री को [-1,-1,-1,-1,-1] से प्रारंभ करें, फिर find(1), find(3) और find(5) कॉल करें
आउटपुट
1 1 0
