1261. Find Elements in a Contaminated Binary Tree Medium

1/**
2 * [1261] Find Elements in a Contaminated Binary Tree
3 *
4 * Given a binary tree with the following rules:
5 * <ol>
6 * 	root.val == 0
7 * 	If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1
8 * 	If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2
9 * </ol>
10 * Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.
11 * Implement the FindElements class:
12 * 
13 * 	FindElements(TreeNode* root) Initializes the object with a contaminated binary tree and recovers it.
14 * 	bool find(int target) Returns true if the target value exists in the recovered binary tree.
15 * 
16 *  
17 * Example 1:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2019/11/06/untitled-diagram-4-1.jpg" style="width: 320px; height: 119px;" />
19 * Input
20 * ["FindElements","find","find"]
21 * [[[-1,null,-1]],[1],[2]]
22 * Output
23 * [null,false,true]
24 * Explanation
25 * FindElements findElements = new FindElements([-1,null,-1]); 
26 * findElements.find(1); // return False 
27 * findElements.find(2); // return True 
28 * Example 2:
29 * <img alt="" src="https://assets.leetcode.com/uploads/2019/11/06/untitled-diagram-4.jpg" style="width: 400px; height: 198px;" />
30 * Input
31 * ["FindElements","find","find","find"]
32 * [[[-1,-1,-1,-1,-1]],[1],[3],[5]]
33 * Output
34 * [null,true,true,false]
35 * Explanation
36 * FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
37 * findElements.find(1); // return True
38 * findElements.find(3); // return True
39 * findElements.find(5); // return False
40 * Example 3:
41 * <img alt="" src="https://assets.leetcode.com/uploads/2019/11/07/untitled-diagram-4-1-1.jpg" style="width: 306px; height: 274px;" />
42 * Input
43 * ["FindElements","find","find","find","find"]
44 * [[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
45 * Output
46 * [null,true,false,false,true]
47 * Explanation
48 * FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
49 * findElements.find(2); // return True
50 * findElements.find(3); // return False
51 * findElements.find(4); // return False
52 * findElements.find(5); // return True
53 * 
54 *  
55 * Constraints:
56 * 
57 * 	TreeNode.val == -1
58 * 	The height of the binary tree is less than or equal to 20
59 * 	The total number of nodes is between [1, 10^4]
60 * 	Total calls of find() is between [1, 10^4]
61 * 	0 <= target <= 10^6
62 * 
63 */
64pub struct Solution {}
65use crate::util::tree::{TreeNode, to_tree};
66
67// problem: https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/
68// discuss: https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/discuss/?currentPage=1&orderBy=most_votes&query=
69
70// submission codes start here
71
72// Definition for a binary tree node.
73// #[derive(Debug, PartialEq, Eq)]
74// pub struct TreeNode {
75//   pub val: i32,
76//   pub left: Option<Rc<RefCell<TreeNode>>>,
77//   pub right: Option<Rc<RefCell<TreeNode>>>,
78// }
79// 
80// impl TreeNode {
81//   #[inline]
82//   pub fn new(val: i32) -> Self {
83//     TreeNode {
84//       val,
85//       left: None,
86//       right: None
87//     }
88//   }
89// }
90struct FindElements {
91        false
92    }
93
94
95/** 
96 * `&self` means the method takes an immutable reference.
97 * If you need a mutable reference, change it to `&mut self` instead.
98 */
99impl FindElements {
100
101    fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
102        
103    }
104    
105    fn find(&self, target: i32) -> bool {
106        
107    }
108}
109
110/**
111 * Your FindElements object will be instantiated and called as such:
112 * let obj = FindElements::new(root);
113 * let ret_1: bool = obj.find(target);
114 */
115
116// submission codes end
117
118#[cfg(test)]
119mod tests {
120    use super::*;
121
122    #[test]
123    fn test_1261() {
124    }
125}
126