Skip to content

1261. Find Elements in a Contaminated Binary Tree 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class FindElements {
 public:
  FindElements(TreeNode* root) {
    dfs(root, 0);
  }

  bool find(int target) {
    return vals.contains(target);
  }

 private:
  unordered_set<int> vals;

  void dfs(TreeNode* root, int val) {
    if (root == nullptr)
      return;

    root->val = val;
    vals.insert(val);
    dfs(root->left, val * 2 + 1);
    dfs(root->right, val * 2 + 2);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class FindElements {
  public FindElements(TreeNode root) {
    dfs(root, 0);
  }

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

  private Set<Integer> vals = new HashSet<>();

  private void dfs(TreeNode root, int val) {
    if (root == null)
      return;

    root.val = val;
    vals.add(val);
    dfs(root.left, val * 2 + 1);
    dfs(root.right, val * 2 + 2);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class FindElements:
  def __init__(self, root: TreeNode | None):
    self.vals = set()
    self.dfs(root, 0)

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

  def dfs(self, root: TreeNode | None, val: int) -> None:
    if not root:
      return

    root.val = val
    self.vals.add(val)
    self.dfs(root.left, val * 2 + 1)
    self.dfs(root.right, val * 2 + 2)