#1261

Find Elements in a Contaminated Binary Tree

pupil · 405 · lc medium +24 · 84.1% accepted · 1,429 likes · top 95%

Description

A binary tree originally obeyed these rules:

- root.val == 0

- For any node with value x: the left child (if present) has value 2 * x + 1, and the right child (if present) has value 2 * x + 2.

All node values have been replaced with -1 (contaminated). Recover the tree and support value lookups.

Implement FindElements:

- FindElements(TreeNode* root) restores the tree using the rules above.

- bool find(int target) returns true if target appears in the recovered 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

Code

# 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 find(self, target: int) -> bool:
        


# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)

# 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 find(self, target: int) -> bool:
        


# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)