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

Arnab Chakraborty

更新于:08-06-2020

201 次浏览

开启你的 职业生涯

完成课程后获得认证

开始