সি++-এ বাইনারি ট্রি ক্যামেরা

মান লিইয়ে নিই একটি বাইনারি ট্রি রয়েছে; আমরা ট্রির নোডগুলোর ওপর ক্যামেরা রাখি। এখন প্রতিটি ক্যামেরা একটি নোডে থাকলে তার প্যারেন্ট, নিজে এবং এর চাইল্ডদের মনিটর করতে পারে। আমাদের ট্রির সব নোড মনিটর করার জন্য ন্যূনতম কতটি ক্যামেরা লাগবে তা বের করতে হবে।

সুতরাং, যদি ইনপুট হয়:

তব আউটপুট হবে ১, কারণ শুধু একটি ক্যামেরা সব ট্র্যাক করার জন্য পর্যাপ্ত।

समाधान पद्धति

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• TreeNode টাইপের একটি covered নামক সেট সংজ্ঞায়িত করুন (Tree node-এ left, right এবং data ফিল্ড থাকে)
• solve() ফাংশন সংজ্ঞায়িত করুন, যা node, parent গ্রহণ করবে,
• যদি node null হয়, তবে:
  • ফেরত দিন
• solve(নোডের বাম, নোড)
• solve(নোডের ডান, নোড)
• যদি (parent NULL-এর সমান হয় এবং (node, নোডের বাম, নোডের ডান) কিছুই কভারড না হয়), তবে:
  • (ans 1 বাড়ান)
  • node কে covered-এ যোগ করুন
  • নোডের বাম কে covered-এ যোগ করুন
  • নোডের ডান কে covered-এ যোগ করুন
  • parent কে covered-এ যোগ করুন
• মূল পদ্ধতিতে নিম্নলিখিত কাজ করুন:
  • ans := 0
  • NULL কে covered-এ যোগ করুন
  • solve(root, 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