数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服饰学
法学C++ 中的二叉树中的摄像头
假设我们有一棵二叉树；我们在树节点上放置摄像头。现在，节点上的每个摄像头都可以监控其父节点、自身及其子节点。我们必须找到监测树的所有节点所需的摄像头最低数量。
因此，如果输入如下所示 -
那么输出将为 1，因为只需要一个摄像头就可以追踪所有。
要解决这个问题，我们将遵循以下步骤 -
定义名为 covered 的集合，类型为 TreeNode（树节点具有 left、right 和 data 字段）
定义函数 solve()，这将采用 node、parent，
如果 node 为 null，则 -
返回
solve(node 的左侧、node)
solve(node 的右侧、node)
如果 (parent 与 NULL 相同并且 (node、node 的左侧、node 的右侧) 没有被覆盖，则 -
(增加 ans 为 1)
将 node 插入到 covered 中
将 node 的左侧插入到 covered 中
将 node 的右侧插入到 covered 中
将 parent 插入到 covered 中
在主要方法中执行以下操作，
ans := 0
在覆盖中插入 NULL
solve(根, NULL)
返回 ans
让我们查看以下实现，以获得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = NULL;
right = NULL;
}
};
class Solution {
public:
set<TreeNode*> covered;
int ans;
int minCameraCover(TreeNode* root){
covered.clear();
ans = 0;
covered.insert(NULL);
solve(root, NULL);
return ans;
}
void solve(TreeNode* node, TreeNode* parent){
if (!node)
return;
solve(node->left, node);
solve(node->right, node);
if ((parent == NULL && covered.find(node) == covered.end())
|| covered.find(node->left) == covered.end() || covered.find(node-
>right) == covered.end()) {
ans++;
covered.insert(node);
covered.insert(node->left);
covered.insert(node->right);
covered.insert(parent);
}
}
};
main(){
Solution ob;
TreeNode *root = new TreeNode(1);
root->left = new TreeNode(1);
root->left->left = new TreeNode(1); root->left->right = new
TreeNode(1);
cout << (ob.minCameraCover(root));
}输入
[1,1,NULL,1,1]
输出
1
更新于:08-06-2020
201 次浏览
广告