Leetcode Problem:
Summary
- The problem requires to recover a binary tree from a contaminated tree where all node values are -1 and then find if a target value exists in the recovered tree.
Approach
- The solution uses a helper function traversal to populate a boolean array s with the original values of the binary tree
- The traversal function is a depth-first search that assigns the original values to the nodes and marks them in the s array
- The find function simply checks the s array for the target value.
Complexity
- O(n), where n is the number of nodes in the tree, because each node is visited once during the traversal.
Explanation
- The solution uses a boolean array s of size 2000001 to keep track of the original values of the nodes
- The traversal function is a recursive depth-first search that assigns the original values to the nodes and marks them in the s array
- The find function simply checks the s array for the target value
- This approach ensures that the original values are recovered and can be used to check for the existence of a target value.
Solution Code:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class FindElements {
public:
bool s[2000001] = {0};
void traversal(TreeNode* root, int val){
if(root == nullptr) return;
root->val = val;
s[val] = true;
traversal(root->left, val*2 + 1);
traversal(root->right, val*2 + 2);
}
FindElements(TreeNode* root) {
traversal(root, 0);
}
bool find(int target) {
return s[target];
}
};
/**
* Your FindElements object will be instantiated and called as such:
* FindElements* obj = new FindElements(root);
* bool param_1 = obj->find(target);
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class FindElements {
public:
bool s[2000001] = {0};
void traversal(TreeNode* root, int val){
if(root == nullptr) return;
root->val = val;
s[val] = true;
traversal(root->left, val*2 + 1);
traversal(root->right, val*2 + 2);
}
FindElements(TreeNode* root) {
traversal(root, 0);
}
bool find(int target) {
return s[target];
}
};
/**
* Your FindElements object will be instantiated and called as such:
* FindElements* obj = new FindElements(root);
* bool param_1 = obj->find(target);
*/
'알고리즘' 카테고리의 다른 글
| Shortest Subarray with Sum at Least K (0) | 2025.02.22 |
|---|---|
| Find the Power of K-Size Subarrays I (0) | 2025.02.22 |
| Shortest Subarray to be Removed to Make Array Sorted (0) | 2025.02.21 |
| Minimized Maximum of Products Distributed to Any Store (0) | 2025.02.21 |
| Count the Number of Fair Pairs (0) | 2025.02.21 |
짬뽕얼큰하게
