Algorithm

Problem Name: 1261. Find Elements in a Contaminated Binary Tree

Problem Link: https://leetcode.com/problems/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;
    }
    set.add(value);
    recover(root.left, 2 * value + 1);
    recover(root.right, 2 * value + 2);
  }

  public boolean find(int target) {
    return set.contains(target);
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["FindElements","find","find"] [[[-1,null,-1]],[1],[2]]

Output

x
–
+
cmd
[null,false,true]

#2 Code Example with Javascript Programming

Code - Javascript Programming


const FindElements = function(root) {
  this.root = root
  this.set = new Set()
  if(root) this.set.add(0)
  
  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
      set.add(child)
      dfs(node.left, child, set)
    }
    if(node.right) {      
      const child = cur * 2 + 2
      set.add(child)
      dfs(node.right, child, set)
    }
  }
};

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

Input

x
–
+
cmd
["FindElements","find","find"] [[[-1,null,-1]],[1],[2]]

Output

x
–
+
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.nums.add(node.val)
            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 & Try With Live Editor

Input

x
–
+
cmd
["FindElements","find","find","find"] [[[-1,-1,-1,-1,-1]],[1],[3],[5]]

Output

x
–
+
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;
            values.Add(value);
            Recover(node.left, 2 * value + 1);
            Recover(node.right, 2 * value + 2);
        }
    }

}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["FindElements","find","find","find"] [[[-1,-1,-1,-1,-1]],[1],[3],[5]]

Output

x
–
+
cmd
[null,true,true,false]
Advertisements

Demonstration

Previous
#1260 Leetcode Shift 2D Grid Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#1262 Leetcode Greatest Sum Divisible by Three Solution in C, C++, Java, JavaScript, Python, C# Leetcode