# 1261. Find Elements in a Contaminated Binary Tree

Given a binary tree with the following rules:

1. `root.val == 0`
2. If `treeNode.val == x` and `treeNode.left != null`, then `treeNode.left.val == 2 * x + 1`
3. If `treeNode.val == x` and `treeNode.right != null`, then `treeNode.right.val == 2 * x + 2`

Now the binary tree is contaminated, which means all `treeNode.val` have been changed to `-1`.

Implement the `FindElements` class:

• `FindElements(TreeNode* root)` Initializes the object with a contaminated binary tree and recovers it.
• `bool find(int target)` Returns `true` if the `target` value exists in the recovered binary tree.

Example 1:

``````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:

``````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:

``````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 == -1`
• The height of the binary tree is less than or equal to `20`
• The total number of nodes is between `[1, 10^4]`
• Total calls of `find()` is between `[1, 10^4]`
• `0 <= target <= 106`

``````class FindElements {
public:
FindElements(TreeNode* root) {
helper(root, 0);
}

bool find(int target) {
return st.count(target);
}

private:
unordered_set<int> st;

void helper(TreeNode* node, int val) {
if (!node) return;
st.insert(val);
node->val = val;
if (node->left) helper(node->left, 2 * val + 1);
if (node->right) helper(node->right, 2 * val + 2);
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1261

https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/

https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/discuss/431107/JavaPython-3-DFS-and-BFS-clean-codes-w-analysis.

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation