数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法律在 C++ 中查找污染二叉树中的元素
假设我们有一个二叉树。该树的规则如下：
根节点的值为 0
如果树节点的值为 x 且树节点的左子节点不为空，则树节点的左子节点的值为 2 * x + 1
如果树节点的值为 x 且树节点的右子节点不为空，则树节点的右子节点的值为 2 * x + 2
现在，由于二叉树被污染了。这意味着树节点的所有值都已更改为 -1。我们必须首先恢复二叉树，然后实现 FindElements 类，如下所示：
FindElements(TreeNode* root) 使用污染的二叉树初始化对象，我们必须首先恢复它。
bool find(int target)。这将返回目标值是否存在于恢复的二叉树中。
所以如果树是这样的：
因此，在恢复之后，如果我们尝试查找 1、3 和 5，则结果将分别为 true、true 和 false。
为了解决这个问题，我们将遵循以下步骤：
定义一个集合 a
定义一个 dfs() 方法，它将接收根节点和 rootVal。rootVal 最初为 -1
如果根节点为空，则返回
如果 rootVal 为 -1，则将根节点的值设置为 0，否则将其设置为 rootVal
将根节点的值插入到 a 中
调用 dfs(根节点的左子节点, 2 * 根节点的值 + 1), dfs(根节点的右子节点, 2 * 根节点的值 + 2)
对于初始化（或重建），我们将调用 dfs(根节点, -1)
要查找某个元素，请检查该元素是否在 a 中，如果在则返回 true，否则返回 false。
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
}else{
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class FindElements {
public:
set <int> a;
void dfs(TreeNode* root,int rootVal=-1){
if(!root)return;
root->val = rootVal == -1?0:rootVal;
a.insert(root->val);
dfs(root->left,2*root->val + 1);
dfs(root->right, 2*root->val + 2);
}
FindElements(TreeNode* root) {
dfs(root);
}
bool find(int t) {
return a.find(t)!=a.end();
}
};
main(){
vector<int> v = {-1,-1,-1,-1,-1};
TreeNode *root = make_tree(v);
FindElements ob(root);
cout << (ob.find(1)) << endl;
cout << (ob.find(3)) << endl;
cout << (ob.find(5)) << endl;
}输入
Initialize the tree with [-1,-1,-1,-1,-1], then call find(1), find(3) and find(5)
输出
1 1 0
更新于: 2020年5月2日
154 次浏览
广告