C++ 中的二叉树相机
c++server side programmingprogramming
假设我们有一个二叉树；我们将相机放置在树的节点上。现在，节点上的每个相机都可以监控其父节点、自身及其子节点。我们必须找到监控树的所有节点所需的最少相机数量。
因此，如果输入为 −
则输出将为 1，因为仅需一个摄像头就足以跟踪所有。
为了解决这个问题，我们将遵循以下步骤 −
定义一个名为 covered 的集合，类型为 TreeNode(树节点具有左、右和数据字段)
定义一个函数 resolve()，它将获取节点、父节点，
如果节点为空，则 −
返回
solve(节点左侧，节点)
solve(节点右侧，节点)
如果(父节点与 NULL 相同且(节点、节点左侧、节点右侧)则无covered，然后减去；
(将 ans 增加 1)
将节点插入covered
将节点左侧插入covered
将节点右侧插入covered
将父节点插入covered
从主方法执行以下操作，
ans := 0
将 NULL 插入covered
solve(root, NULL)
return 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
