मान लीजिए हमारे पास एक बाइनरी ट्री है; हम ट्री के नोड्स पर कैमरे लगाते हैं। अब प्रत्येक कैमरा एक नोड पर अपने माता-पिता, स्वयं और अपने बच्चों की निगरानी कर सकता है। हमें ट्री के सभी नोड्स की निगरानी के लिए आवश्यक कैमरों की न्यूनतम संख्या ज्ञात करनी है।
यदि इनपुट है -
तो आउटपुट 1 होगा, क्योंकि सभी को ट्रैक करने के लिए केवल एक कैमरा पर्याप्त है।
हल करने के चरण
TreeNode प्रकार का एक सेट covered परिभाषित करें
solve() फ़ंक्शन परिभाषित करें जो नोड, पैरेंट लेता है
यदि नोड नल है तो वापस लौटें
बाएं और दाएं बच्चे पर पुनरावर्ती कॉल करें
यदि (पैरेंट नल है और (नोड, बायां, दायां) में से कुछ भी कवर नहीं है) या बायां/दायां कवर नहीं है तो: ans बढ़ाएं, नोड, बाएं, दाएं, पैरेंट को 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);
}
}
};
int 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));
return 0;
}
इनपुट
[1,1,NULL,1,1]
आउटपुट
1
