| comments | difficulty | edit_url | rating | source | tags | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
1439 |
第 163 场周赛 Q2 |
|
给出一个满足下述规则的二叉树：
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
提示：
TreeNode.val == -1- 二叉树的高度不超过
20 - 节点的总数在
[1, 10^4]之间 - 调用
find()的总次数在[1, 10^4]之间 0 <= target <= 10^6
我们先通过 DFS 遍历二叉树，将节点值恢复为原来的值，并将所有节点值存入哈希表中。然后在查找时，只需要判断哈希表中是否存在目标值即可。
时间复杂度方面，初始化时需要遍历二叉树，时间复杂度为
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class FindElements:
def __init__(self, root: Optional[TreeNode]):
def dfs(root: Optional[TreeNode]):
self.s.add(root.val)
if root.left:
root.left.val = root.val * 2 + 1
dfs(root.left)
if root.right:
root.right.val = root.val * 2 + 2
dfs(root.right)
root.val = 0
self.s = set()
dfs(root)
def find(self, target: int) -> bool:
return target in self.s
# Your FindElements object will be instantiated and called as such:
# obj = FindElements(root)
# param_1 = obj.find(target)/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class FindElements {
private Set<Integer> s = new HashSet<>();
public FindElements(TreeNode root) {
root.val = 0;
dfs(root);
}
public boolean find(int target) {
return s.contains(target);
}
private void dfs(TreeNode root) {
s.add(root.val);
if (root.left != null) {
root.left.val = root.val * 2 + 1;
dfs(root.left);
}
if (root.right != null) {
root.right.val = root.val * 2 + 2;
dfs(root.right);
}
}
}
/**
* Your FindElements object will be instantiated and called as such:
* FindElements obj = new FindElements(root);
* boolean param_1 = obj.find(target);
*//**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class FindElements {
public:
FindElements(TreeNode* root) {
root->val = 0;
dfs(root);
}
bool find(int target) {
return s.contains(target);
}
private:
unordered_set<int> s;
void dfs(TreeNode* root) {
s.insert(root->val);
if (root->left) {
root->left->val = root->val * 2 + 1;
dfs(root->left);
}
if (root->right) {
root->right->val = root->val * 2 + 2;
dfs(root->right);
}
};
};
/**
* Your FindElements object will be instantiated and called as such:
* FindElements* obj = new FindElements(root);
* bool param_1 = obj->find(target);
*//**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type FindElements struct {
s map[int]bool
}
func Constructor(root *TreeNode) FindElements {
root.Val = 0
s := map[int]bool{}
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
s[root.Val] = true
if root.Left != nil {
root.Left.Val = root.Val*2 + 1
dfs(root.Left)
}
if root.Right != nil {
root.Right.Val = root.Val*2 + 2
dfs(root.Right)
}
}
dfs(root)
return FindElements{s}
}
func (this *FindElements) Find(target int) bool {
return this.s[target]
}
/**
* Your FindElements object will be instantiated and called as such:
* obj := Constructor(root);
* param_1 := obj.Find(target);
*//**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
class FindElements {
private s: Set<number> = new Set<number>();
constructor(root: TreeNode | null) {
root.val = 0;
const dfs = (root: TreeNode) => {
this.s.add(root.val);
if (root.left) {
root.left.val = root.val * 2 + 1;
dfs(root.left);
}
if (root.right) {
root.right.val = root.val * 2 + 2;
dfs(root.right);
}
};
dfs(root);
}
find(target: number): boolean {
return this.s.has(target);
}
}
/**
* Your FindElements object will be instantiated and called as such:
* var obj = new FindElements(root)
* var param_1 = obj.find(target)
*/