给出一个满足下述规则的二叉树:
请你先还原二叉树,然后实现 FindElements 类:
FindElements(TreeNode* root)
用受污染的二叉树初始化对象,你需要先把它还原。bool find(int target)
判断目标值 target 是否存在于还原后的二叉树中并返回结果。提示:
TreeNode.val == -1
二叉树的高度不超过 20
节点的总数在 [1, 10^4] 之间
调用 find() 的总次数在 [1, 10^4] 之间
0 <= target <= 10^6
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/find-elements-in-a-contaminated-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/find-elements-in-a-contaminated-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class FindElements {
unordered_set<int> s;
public:
FindElements(TreeNode* root) {
dfs(root,0);
}
void dfs(TreeNode* root, int val)
{
if(root == NULL)
return;
s.insert(val);
dfs(root->left,(val<<1)+1);
dfs(root->right,(val<<1)+2);
}
bool find(int target) {
return s.count(target);
}
};
class FindElements {
unordered_set<int> s;
public:
FindElements(TreeNode* root) {
queue<pair<TreeNode*,int>> q;
q.push(make_pair(root,0));
pair<TreeNode*,int> tp;
while(!q.empty())
{
tp = q.front();
q.pop();
s.insert(tp.second);
if(tp.first->left)
q.push(make_pair(tp.first->left, (tp.second<<1)+1));
if(tp.first->right)
q.push(make_pair(tp.first->right, (tp.second<<1)+2));
}
}
bool find(int target) {
return s.count(target);
}
};