मान लीजिए हमारे पास एक बाइनरी ट्री है; हम पेड़ के नोड्स पर कैमरे लगाते हैं। अब नोड पर प्रत्येक कैमरा अपने माता-पिता, स्वयं और उसके बच्चों की निगरानी कर सकता है। हमें पेड़ के सभी नोड्स की निगरानी के लिए आवश्यक न्यूनतम कैमरों की संख्या ढूंढनी होगी।
तो, अगर इनपुट की तरह है -
तो आउटपुट 1 होगा, क्योंकि सभी को ट्रैक करने के लिए केवल एक कैमरा ही काफी है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
कवर नामक एक सेट को परिभाषित करें, टाइप ट्रीनोड (ट्री नोड में बाएं, दाएं और डेटा फ़ील्ड है)
-
फ़ंक्शन को हल करें () को परिभाषित करें, यह नोड, पैरेंट,
ले जाएगा -
यदि नोड शून्य है, तो -
-
वापसी
-
-
हल करें (नोड के बाएं, नोड)
-
हल करें (नोड का दायां, नोड)
-
अगर (पैरेंट NULL के समान है और (नोड, नोड के बाएं, नोड के दाएं) कुछ भी कवर नहीं किया गया है, तो -
-
(उत्तर 1 से बढ़ाएँ)
-
कवर में नोड डालें
-
नोड के बाईं ओर कवर में डालें
-
नोड के दाएं को कवर में डालें
-
माता-पिता को कवर में डालें
-
-
मुख्य विधि से निम्न कार्य करें,
-
उत्तर:=0
-
कवर में NULL डालें
-
हल करें (रूट, न्यूल)
-
वापसी उत्तर
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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