Find Elements in a Contaminated Binary Tree
Problem Statement
Tumhe ek binary tree diya gaya hai jisme kuch rules hain:
root.val== 0
Kisi bhi treeNode ke liye:
Agar treeNode.valka value x hai aur treeNode.left!= null, toh treeNode.left.val== 2 * x + 1
Agar treeNode.valka value x hai aur treeNode.right!= null, toh treeNode.right.val== 2 * x + 2
Ab yeh binary tree contaminate ho gaya hai, matlab sabhi treeNode.val-1 mein badal chuke hain.
Tumhe FindElements class implement karna hai:
FindElements(TreeNode root)*: Yeh object initialize karega ek contaminated binary tree se aur usko recover karega.
bool find(int target): Yeh method return karega true agar target value recovered binary tree mein exist karti hai.
Example
Example 1:
plaintext
Input
[“FindElements”,”find”,”find”]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]
Explanation:
FindElements findElements = new FindElements([-1,null,-1]);
findElements.find(1); // return False
findElements.find(2); // return True
Example 2:
plaintext
Input
[“FindElements”,”find”,”find”,”find”]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
Output
[null,true,true,false]
Explanation:
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False
Example 3:
plaintext
Input
[“FindElements”,”find”,”find”,”find”,”find”]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
Output
[null,true,false,false,true]
Explanation:
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2); // return True
findElements.find(3); // return False
findElements.find(4); // return False
findElements.find(5); // return True
Constraints
TreeNode.val== -1Binary tree ki height maximum 20 tak ho sakti hai.
Total number of nodes 1 se 10^4 ke beech mein hain.
find() ke total calls 1 se 10^4 ke beech mein hain.
0 <= target <= 10^6.
Find Elements in a Contaminated Binary Tree
Recovery Rules:
Sabse pehle, contaminated tree ko recover karna hota hai. Root se shuruaat karte hain aur baaki nodes ko specific rules ke according set karte hain.
Yeh rules ensure karte hain ki har node ka value unique hoga aur sahi tarike se calculate hoga:
Agar kisi treeNode ka value x hai aur treeNode.left exist karta hai, to treeNode.left.val hoga 2 * x + 1.
Agar kisi treeNode ka value x hai aur treeNode.right exist karta hai, to treeNode.right.val hoga 2 * x + 2.
Efficient Lookup:
Recovery ke baad, hum target value ko quickly find kar sakte hain.Iske liye, hum BitSet ya set use karte hain jo O(1) lookup time allow karta hai.
Optimal Time Complexity: Tree Recovery: Pure tree ko recover karne ke liye humein O(n) time lagta hai, jahan n total number of nodes hai.
Find Operation: Har find operation O(1) time leta hai, kyunki hum directly BitSet ya set mein check karte hain.
Time Complexity:
O(n) for Recovery:
Jab hum tree ko recover karte hain, toh humein sabhi nodes ko ek baar traverse karna padta hai. Isme n nodes hain, toh overall time complexity O(n) ho jaati hai.
O(1) for Each
findOperation:Har
findoperation ke liye humein seedha BitSet ya set mein value check karni hoti hai. Ye operation constant time mein ho jaata hai, yani O(1) time lagta hai.
Space Complexity:
O(n) for Storing Recovered Node Values:
Jab hum nodes recover karte hain, toh humein un sabhi recovered nodes ko store karna hota hai. Total n nodes hain, isliye space complexity O(n) hoti hai.
Solution
// FindElements class ka constructor
var FindElements = function(root) {
// Recovered values ko store karne ke liye Set banate hain
this.recoveredValues = new Set();
// Root ka value recover karte hain
root.val = 0;
// Tree ko recover karne ka method call karte hain
this.recoverTree(root);
};
// Tree ko recover karne ka method
FindElements.prototype.recoverTree = function(root) {
// Agar root null hai toh return karte hain
if (!root) return;
// Current node ka value Set mein add karte hain
this.recoveredValues.add(root.val);
// Agar left child exist karta hai
if (root.left) {
// Left child ka value calculate karte hain
root.left.val = 2 * root.val + 1;
// Recursively left child ke liye recoverTree method call karte hain
this.recoverTree(root.left);
}
// Agar right child exist karta hai
if (root.right) {
// Right child ka value calculate karte hain
root.right.val = 2 * root.val + 2;
// Recursively right child ke liye recoverTree method call karte hain
this.recoverTree(root.right);
}
};
// Target value find karne ka method
FindElements.prototype.find = function(target) {
// Check karte hain agar target value Set mein hai
return this.recoveredValues.has(target);
};
Yeh code ek class FindElements banata hai jo contaminated binary tree ko recover karta hai aur target values ko efficiently dhoondh sakta hai. Pehle, constructor method mein ek set banate hain jisme recovered values store hoti hain. Fir, root node ka value 0 set karte hain aur ek method call karte hain jo poore tree ko recursively recover karta hai.
RecoverTree Method:
Ye method har node ko check karta hai. Agar node null nahi hai, toh uska value set mein add karta hai.
Fir, left aur right children ke values calculate karke unhe set karta hai.
Left child ka value hota hai 2 * current node value + 1, aur right child ka value hota hai 2 * current node value + 2.
Yeh process recursively poore tree ke liye follow hota hai, jab tak saare nodes recover na ho jayein.
Find Method:
Ye method directly set mein check karta hai agar target value exist karti hai ya nahi.
Agar target value set mein hai, toh true return karta hai, warna false.
Solution
class FindElements {
// Recovered values ko store karne ke liye unordered_set banate hain
unordered_set<int> recoveredValues;
// Tree ko recover karne ka method
void recoverTree(TreeNode* root) {
// Agar root null hai toh return karte hain
if (!root) return;
// Current node ka value set mein insert karte hain
recoveredValues.insert(root->val);
// Agar left child exist karta hai
if (root->left) {
// Left child ka value calculate karte hain
root->left->val = 2 * root->val + 1;
// Recursively left child ke liye recoverTree method call karte hain
recoverTree(root->left);
}
// Agar right child exist karta hai
if (root->right) {
// Right child ka value calculate karte hain
root->right->val = 2 * root->val + 2;
// Recursively right child ke liye recoverTree method call karte hain
recoverTree(root->right);
}
}
public:
// FindElements class ka constructor
FindElements(TreeNode* root) {
// Root ka value recover karte hain
root->val = 0;
// Tree ko recover karne ka method call karte hain
recoverTree(root);
}
// Target value find karne ka method
bool find(int target) {
// Check karte hain agar target value set mein hai
return recoveredValues.count(target);
}
};
