# Leetcode - Find Elements in a Contaminated Binary Tree

violet posted @ May 21, 2020 05:42:37 AM in 算法 with tags Algorithm Golang tree DFS , 298 阅读

https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/

Given a binary tree with the following rules:

1. `root.val == 0`
2. If `treeNode.val == x` and `treeNode.left != null`, then `treeNode.left.val == 2 * x + 1`
3. If `treeNode.val == 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`.

You need to first recover the binary tree and then implement the `FindElements` class:

• `FindElements(TreeNode* root)` Initializes the object with a contamined binary tree, you need to recover it first.
• `bool find(int target)` Return if the `target` value exists in the recovered binary tree.

Example 1:

```Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]
Explanation
FindElements findElements = new FindElements([-1,null,-1]);
findElements.find(1); // return False
findElements.find(2); // return True ```

`Contaminated` only means it has a default value. No need to consider what kind of shit that it stores.

```/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
type FindElements struct {
root *TreeNode
hash map[int]bool
}

func Constructor(root *TreeNode) FindElements {
hash := map[int]bool{}
dfs(root, 0, &hash)
return FindElements{
root: root,
hash: hash,
}
}

func dfs(root *TreeNode, val int, hash *map[int]bool) {
if root == nil {
return
}
(*hash)[val] = true
root.Val = val
dfs(root.Left, 2*val+1, hash)
dfs(root.Right, 2*val+2, hash)
}

func (this *FindElements) Find(target int) bool {
return this.hash[target]
}

/**
* Your FindElements object will be instantiated and called as such:
* obj := Constructor(root);
* param_1 := obj.Find(target);
*/```

(输入验证码)
or Ctrl+Enter