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.


&nbsp;
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


&nbsp;
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 &lt;= target &lt;= 106


# 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 recoverTree(root):
            if not root:
                return None
            self.vals.add(root.val)
            if root.left:
                root.left.val = 2 * root.val + 1
                recoverTree(root.left)
            if root.right:
                root.right.val = 2 * root.val + 2
                recoverTree(root.right)
        self.vals = set()
        root.val = 0
        recoverTree(root)

    def find(self, target: int) -> bool:
        return target in self.vals

# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)
class FindElements {
    TreeNode tree,nodept;
    public FindElements(TreeNode root) {
        tree=root;
        tree.val=0;
        go(tree);
    }

    void go(TreeNode node){
        if(node.left!=null){
            node.left.val=node.val*2+1;
            go(node.left);
        }
        if(node.right!=null){
            node.right.val=node.val*2+2;
            go(node.right);
        }
    }

    public boolean find(int target) {
        return doit(target);
    }

    boolean doit(int target){
        if(target==0){
            nodept=tree;
            return true;
        }
        boolean f=doit((target-1)/2);
        if(!f)return false;
        if(nodept.left!=null && nodept.left.val==target)
            nodept=nodept.left;
        else if(nodept.right!=null && nodept.right.val==target)
            nodept=nodept.right;
        else f=false;
        return f;
    }
}
/**
 * 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:
    void initialize(TreeNode* root,unordered_set<int> &s){
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            auto t = q.front();
            q.pop();
            s.insert(t->val);
            if(t->left != NULL){
                t->left->val = 2*(t->val)+1;
                q.push(t->left);
            }
            if(t->right != NULL){
                t->right->val= 2*(t->val)+2;
                q.push(t->right);
            }
        }
    }
    unordered_set<int> s;
    FindElements(TreeNode* root) {
        root->val = 0;
        

        initialize(root,s);
        
    }
    
    bool find(int target) {
        if(s.find(target) != s.end())
            return true;
        return false;
    }
};

/**
 * 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.
 * function TreeNode(val, left, right) {
 * this.val = (val===undefined ? 0 : val)
 * this.left = (left===undefined ? null : left)
 * this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 */
var FindElements = function(root) {
    this.st = new Set()

    recover = (root, val) =>{
    this.st.add(val);
    if(root.left != null) recover(root.left, val * 2 + 1)
    if(root.right != null) recover(root.right, val * 2 + 2)
    }

    recover(root, 0)
};

/**
 * @param {number} target
 * @return {boolean}
 */
FindElements.prototype.find = function(target) {
    return this.st.has(target)
};

/**
 * Your FindElements object will be instantiated and called as such:
 * var obj = new FindElements(root)
 * var param_1 = obj.find(target)
 */
Find Elements in a Contaminated Binary Tree