题目描述
给出一个满足下述规则的二叉树:
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
是否存在于还原后的二叉树中并返回结果。
样例
输入:
["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
输入:
["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
输入:
["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
算法
(宽度优先遍历) $O(n)$
- 直接通过遍历一次整个树来恢复,因为树的高度不超过 20,所以可以在恢复过程中使用哈希表记录值。
- 查询时,直接查询哈希表即可。
时间复杂度
- 在建树时仅需要 $O(n)$ 的时间,每次查询的时间为常数。
空间复杂度
- 需要额外 $O(n)$ 的空间用于队列和哈希表。
C++ 代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class FindElements {
public:
unordered_set<int> v;
FindElements(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
root -> val = 0;
while (!q.empty()) {
TreeNode *p = q.front();
q.pop();
v.insert(p -> val);
if (p -> left) {
p -> left -> val = p -> val << 1 | 1;
q.push(p -> left);
}
if (p -> right) {
p -> right -> val = (p -> val + 1) << 1;
q.push(p -> right);
}
}
}
bool find(int target) {
return v.find(target) != v.end();
}
};
/**
* Your FindElements object will be instantiated and called as such:
* FindElements* obj = new FindElements(root);
* bool param_1 = obj->find(target);
*/