Description#
Given a binary tree with the following rules:
root.val == 0- If
treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1 - 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
Solutions#
Solution 1: DFS + Hash Table#
First, we traverse the binary tree using DFS to restore the node values to their original values. Then, we store all node values in a hash table, so we can directly check whether the target value exists in the hash table when searching.
In terms of time complexity, we need to traverse the binary tree during initialization, so the time complexity is $O(n)$. When searching, we only need to check whether the target value exists in the hash table, so the time complexity is $O(1)$. The space complexity is $O(n)$, where $n$ is the number of nodes in the binary tree.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class FindElements:
def __init__(self, root: Optional[TreeNode]):
def dfs(root):
self.vis.add(root.val)
if root.left:
root.left.val = root.val * 2 + 1
dfs(root.left)
if root.right:
root.right.val = root.val * 2 + 2
dfs(root.right)
root.val = 0
self.vis = set()
dfs(root)
def find(self, target: int) -> bool:
return target in self.vis
# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| /**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class FindElements {
private Set<Integer> vis = new HashSet<>();
public FindElements(TreeNode root) {
root.val = 0;
dfs(root);
}
private void dfs(TreeNode root) {
vis.add(root.val);
if (root.left != null) {
root.left.val = root.val * 2 + 1;
dfs(root.left);
}
if (root.right != null) {
root.right.val = root.val * 2 + 2;
dfs(root.right);
}
}
public boolean find(int target) {
return vis.contains(target);
}
}
/**
* Your FindElements object will be instantiated and called as such:
* FindElements obj = new FindElements(root);
* boolean param_1 = obj.find(target);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| /**
* 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:
FindElements(TreeNode* root) {
root->val = 0;
function<void(TreeNode*)> dfs = [&](TreeNode* root) {
vis.insert(root->val);
if (root->left) {
root->left->val = root->val * 2 + 1;
dfs(root->left);
}
if (root->right) {
root->right->val = root->val * 2 + 2;
dfs(root->right);
}
};
dfs(root);
}
bool find(int target) {
return vis.count(target);
}
private:
unordered_set<int> vis;
};
/**
* Your FindElements object will be instantiated and called as such:
* FindElements* obj = new FindElements(root);
* bool param_1 = obj->find(target);
*/
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| /**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type FindElements struct {
vis map[int]bool
}
func Constructor(root *TreeNode) FindElements {
root.Val = 0
vis := map[int]bool{}
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
vis[root.Val] = true
if root.Left != nil {
root.Left.Val = root.Val*2 + 1
dfs(root.Left)
}
if root.Right != nil {
root.Right.Val = root.Val*2 + 2
dfs(root.Right)
}
}
dfs(root)
return FindElements{vis}
}
func (this *FindElements) Find(target int) bool {
return this.vis[target]
}
/**
* Your FindElements object will be instantiated and called as such:
* obj := Constructor(root);
* param_1 := obj.Find(target);
*/
|
