## Algorithm

Problem Name: 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, 104]`
• Total calls of `find()` is between `[1, 104]`
• `0 <= target <= 106`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class FindElements {

private Set set;

public FindElements(TreeNode root) {
set = new HashSet < >();
recover(root, 0);
}

private void recover(TreeNode root, int value) {
if (root == null) {
return;
}
recover(root.left, 2 * value + 1);
recover(root.right, 2 * value + 2);
}

public boolean find(int target) {
return set.contains(target);
}
}
``````
Copy The Code &

Input

cmd
["FindElements","find","find"] [[[-1,null,-1]],[1],[2]]

Output

cmd
[null,false,true]

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const FindElements = function(root) {
this.root = root
this.set = new Set()

dfs(root, 0, this.set)

// console.log(this.set)
function dfs(node, cur, set) {
if(node == null) return

if(node.left) {
const child = cur * 2 + 1
dfs(node.left, child, set)
}
if(node.right) {
const child = cur * 2 + 2
dfs(node.right, child, set)
}
}
};

FindElements.prototype.find = function(target) {
return this.set.has(target)
};
``````
Copy The Code &

Input

cmd
["FindElements","find","find"] [[[-1,null,-1]],[1],[2]]

Output

cmd
[null,false,true]

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class FindElements:
def dfs(self, node: TreeNode, real: int = 0):
if node:
node.val = real
self.dfs(node.left, real * 2 + 1)
self.dfs(node.right, real * 2 + 2)

def __init__(self, root: TreeNode):
self.root = root
self.nums = set()
self.dfs(root)

def find(self, target: int) -> bool:
return target in self.nums
``````
Copy The Code &

Input

cmd
["FindElements","find","find","find"] [[[-1,-1,-1,-1,-1]],[1],[3],[5]]

Output

cmd
[null,true,true,false]

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _1261_FindElementsInAContaminatedBinaryTree
{
private readonly HashSet < int> values;

public _1261_FindElementsInAContaminatedBinaryTree(TreeNode root)
{
values = new HashSet<int>();
Recover(root, 0);
}

public bool Find(int target)
{
return values.Contains(target);
}

private void Recover(TreeNode node, int value)
{
if (node == null) return;
node.val = value;
Recover(node.left, 2 * value + 1);
Recover(node.right, 2 * value + 2);
}
}

}
``````
Copy The Code &

Input

cmd
["FindElements","find","find","find"] [[[-1,-1,-1,-1,-1]],[1],[3],[5]]

Output

cmd
[null,true,true,false]