Find elements in a contaminated binary tree

Hash Table Tree Depth-First Search Breadth-First Search Design Binary Tree

84.1% acceptance

Feb 23, 2026

1429

127

Given a binary tree with the following rules: root.val == 0 For any treeNode: If treeNode.val has a value x and treeNode.left != null, then treeNode.left.val == 2 * x + 1 If treeNode.val has a value 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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashSet;

pub struct FindElements {
  values: HashSet<i32>,
}

impl FindElements {
  pub fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
    let mut values = HashSet::new();
    fn recover(node: &Option<Rc<RefCell<TreeNode>>>, val: i32, values: &mut HashSet<i32>) {
      if let Some(n) = node {
        values.insert(val);
        let n = n.borrow();
        recover(&n.left, 2 * val + 1, values);
        recover(&n.right, 2 * val + 2, values);
      }
    }
    recover(&root, 0, &mut values);
    FindElements { values }
  }

  pub fn find(&self, target: i32) -> bool {
    self.values.contains(&target)
  }
}