|
2 | 2 |
|
3 | 3 | importcom.fishercoder.common.classes.TreeNode; |
4 | 4 |
|
5 | | -/** |
6 | | - * 1261. Find Elements in a Contaminated Binary Tree |
7 | | - * |
8 | | - * Given a binary tree with the following rules: |
9 | | - * root.val == 0 |
10 | | - * If treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1 |
11 | | - * If treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2 |
12 | | - * Now the binary tree is contaminated, which means all treeNode.val have been changed to -1. |
13 | | - * |
14 | | - * You need to first recover the binary tree and then implement the FindElements class: |
15 | | - * FindElements(TreeNode* root) Initializes the object with a contamined binary tree, you need to recover it first. |
16 | | - * bool find(int target) Return if the target value exists in the recovered binary tree. |
17 | | - * |
18 | | - * Example 1: |
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 | | - * |
29 | | - * Example 2: |
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 | | - * |
41 | | - * Example 3: |
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 | | - * Constraints: |
55 | | - * TreeNode.val == -1 |
56 | | - * The height of the binary tree is less than or equal to 20 |
57 | | - * The total number of nodes is between [1, 10^4] |
58 | | - * Total calls of find() is between [1, 10^4] |
59 | | - * 0 <= target <= 10^6 |
60 | | - * */ |
61 | 5 | publicclass_1261 { |
62 | 6 | publicstaticclassSolution1 { |
63 | 7 | classFindElements { |
|