leetcode: 1261: 在受污染的二叉树中查找元素
给出一个满足下述规则的二叉树:
root.val == 0
- 如果
treeNode.val == x
且treeNode.left != null
,那么treeNode.left.val == 2 * x + 1
- 如果
treeNode.val == x
且treeNode.right != null
,那么treeNode.right.val == 2 * x + 2
现在这个二叉树受到「污染」,所有的 treeNode.val
都变成了 -1
。
请你先还原二叉树,然后实现 FindElements
类:
FindElements(TreeNode* root)
用受污染的二叉树初始化对象,你需要先把它还原。bool find(int target)
判断目标值target
是否存在于还原后的二叉树中并返回结果。
示例 1:
输入:
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
输出:
[null,false,true]
解释:
FindElements findElements = new FindElements([-1,null,-1]);
findElements.find(1); // return False
findElements.find(2); // return True
示例 2:
输入:
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出:
[null,true,true,false]
解释:
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False
示例 3:
输入:
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出:
[null,true,false,false,true]
解释:
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
刚看到题目,首先感觉就是填充这个二叉树,将对应节点的val赋值为正确的val,刚写完填充二叉树的代码如下:
1 class FindElements { 2 3 TreeNode root; 4 5 public FindElements(TreeNode root) { 6 this.root = root; 7 init(root, 0); 8 } 9 10 private void init(TreeNode treeNode, int i) { 11 if (treeNode == null) { 12 return; 13 } 14 treeNode.val = i; 15 init(treeNode.left, (i << 1) + 1); 16 init(treeNode.right, (i << 1) + 2); 17 } 18 19 public boolean find(int target) { 20 return false; 21 } 22 }
发现find方法需要查找整棵树,不如遍历一下这个二叉树将所有节点值存到一个集合中,之后在这个集合中查询,然后又发现这个二叉树根本就没有填充的必要,直接在填充时将填充的val放入这个集合中,之后在这个集合中查询就好了.
最终实现代码如下:
1 /** 2 * Definition for a binary tree node. 3 * public class TreeNode { 4 * int val; 5 * TreeNode left; 6 * TreeNode right; 7 * TreeNode() {} 8 * TreeNode(int val) { this.val = val; } 9 * TreeNode(int val, TreeNode left, TreeNode right) { 10 * this.val = val; 11 * this.left = left; 12 * this.right = right; 13 * } 14 * } 15 */ 16 class FindElements { 17 18 Set<Integer> set; 19 20 public FindElements(TreeNode root) { 21 set = new HashSet<>(); 22 init(root, 0); 23 } 24 25 private void init(TreeNode treeNode, int i) { 26 if (treeNode == null) { 27 return; 28 } 29 set.add(i); 30 init(treeNode.left, (i << 1) + 1); 31 init(treeNode.right, (i << 1) + 2); 32 } 33 34 public boolean find(int target) { 35 return set.contains(target); 36 } 37 } 38 39 /** 40 * Your FindElements object will be instantiated and called as such: 41 * FindElements obj = new FindElements(root); 42 * boolean param_1 = obj.find(target); 43 */