Beats 98.92% | DFS | Solution for LeetCode#1261
IntuitionThe problem involves a binary tree that has been "contaminated" by changing all its values to -1. The goal is to "recover" the tree and implement a fin
![image.png](https://assets.leetcode.com/users/images/9898787a-1f21-4ca7-b94d-f7a0d1979ac3_1740101434.9250646.png)


# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The problem involves a binary tree that has been "contaminated" by changing all its values to -1. The goal is to "recover" the tree and implement a find method to determine if a given target value exists in the recovered tree. The recovery process can be derived from the root value and the rules for child nodes: for any node with value x, its left child has value 2 * x + 1 and its right child has value 2 * x + 2.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Recover the Tree: Start by setting the root value to 0 and recursively compute the values of all child nodes using the given rules.
2. Tree Traversal: Implement a helper function to traverse the tree and recover all node values.
3. Find Method: Implement the find method to search for a target value in the recovered tree.

# Complexity
- Time complexity: O(n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(h), where h is the height of the tree.
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code Option-01
![image.png](https://assets.leetcode.com/users/images/2368783c-4b07-479c-9ec7-f4efdee9b9ed_1740101037.6135786.png)
```java []
/**
 * 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 {
    TreeNode groot;

    public FindElements(TreeNode root) {
        if(root!=null && root.val==-1){
            root.val=0;                
        }
        solve1(root);   
        groot=root;  

        //printTree(groot); //Used for printing the new Tree
    }

    void printTree(TreeNode node){
        if(node==null){ 
            System.out.print(" null ");
            return;
        }

        System.out.print(" "+node.val);
        printTree(node.left);
        printTree(node.right);
    }



    void solve1(TreeNode node){
        if(node==null){
            return;
        }

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

        solve1(node.left);
        solve1(node.right);

    }


    
    public boolean find(int target) {
        TreeNode node=new TreeNode();
        node=groot;
        return solve2(node, target);
    }

    boolean solve2(TreeNode node, int target){
        if(node==null){
            return false;
        }
        if(node.val==target){
            return true;
        }
        
        if(solve2(node.left, target) || solve2(node.right, target)) return true;

        return false;
    }  

  
}

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements obj = new FindElements(root);
 * boolean param_1 = obj.find(target);
 */
```



# Code Option-02
![image.png](https://assets.leetcode.com/users/images/143284fe-7038-4875-ac16-98abcc841a49_1740101424.7724223.png)

```java []
/**
 * 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 {
    TreeNode groot;
    Set<Integer> set=new HashSet();

    public FindElements(TreeNode root) {
        if(root!=null && root.val==-1){
            root.val=0;         
            set.add(0);       
        }
        solve1(root);   
        groot=root;  

        //printTree(groot); //Used for printing the new Tree
    }

    void printTree(TreeNode node){
        if(node==null){ 
            System.out.print(" null ");
            return;
        }

        System.out.print(" "+node.val);
        printTree(node.left);
        printTree(node.right);
    }

    void solve1(TreeNode node){
        if(node==null){
            return;
        }

        if(node.left !=null){
            node.left.val=2*node.val+1;   
            set.add(node.left.val);             
        }
        if(node.right !=null){
            node.right.val=2*node.val+2;
            set.add(node.right.val);  
        }

        solve1(node.left);
        solve1(node.right);

    }


    
    public boolean find(int target) {       
        return set.contains(target);
    }

    
}

/**
 * Your FindElements object will be instantiated and called as such:
 * FindElements obj = new FindElements(root);
 * boolean param_1 = obj.find(target);
 */
```
```python []
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class FindElements(object):
    
    def __init__(self, root):
        """
        :type root: Optional[TreeNode]
        """
        self.groot=TreeNode()
        self.sets=set()
        
        if root is not None and root.val==-1:
            root.val=0   
            self.sets.add(root.val) 

        self.solve(root)
        self.groot=root



    def solve(self, node):
        """
        :type node: Optional[TreeNode]
        """
        if node is None:
            return
        
        if node.left is not None:
            node.left.val=2*node.val+1;   
            self.sets.add(node.left.val); 
        
        if node.right is not None:
            node.right.val=2*node.val+2;   
            self.sets.add(node.right.val); 
        
        self.solve(node.left)
        self.solve(node.right)        



    def find(self, target):
        """
        :type target: int
        :rtype: bool
        """
        if target in self.sets:
            return True
        
        return False


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




['Depth-First Search', 'Python', 'Java', 'Python3']