Máy ảnh cây nhị phân trong C ++

Giả sử chúng ta có một cây nhị phân; chúng tôi đặt máy ảnh trên các nút của cây. Giờ đây, mỗi camera tại một nút có thể giám sát cha mẹ, chính nó và các con của nó. Chúng tôi phải tìm số lượng camera tối thiểu cần thiết để giám sát tất cả các nút của cây.

Vì vậy, nếu đầu vào giống như -

thì đầu ra sẽ là 1, vì chỉ một camera là đủ để theo dõi tất cả.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một tập hợp được gọi là được bao phủ, thuộc loại TreeNode (Nút cây có bên trái, bên phải và trường dữ liệu)

• Xác định một hàm giải quyết (), điều này sẽ lấy nút, cha,

• nếu nút là null, thì -

  • trở lại

• giải quyết (bên trái của nút, nút)

• giải quyết (bên phải của nút, nút)

• nếu (cha giống NULL và (nút, bên trái nút, bên phải nút) không có gì bị che, thì -

  • (tăng ans lên 1)

  • chèn nút vào được bao phủ

  • chèn bên trái của nút vào được bao phủ

  • chèn bên phải của nút vào được bao phủ

  • chèn phụ huynh vào được bảo hiểm

• Từ phương thức chính, hãy làm như sau,

• ans:=0

• chèn NULL vào được bao phủ

• giải quyết (root, NULL)

• trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[1,1,NULL,1,1]

Đầu ra

1