मान लीजिए एक चोर ने अपनी चोरी के लिए एक नई जगह ढूंढ ली है। इस क्षेत्र में केवल एक प्रवेश द्वार है, प्रवेश द्वार को "रूट" कहा जाता है। रूट के अलावा, प्रत्येक घर का एक और केवल एक पैरेंट घर होता है। एक दौरे के बाद, स्मार्ट चोर को लगा कि "इस जगह के सभी घर एक बाइनरी ट्री बनाते हैं"। और यदि दो सीधे-लिंक्ड घरों में एक ही रात में चोरी की गई तो यह स्वचालित रूप से पुलिस से संपर्क करेगा। हमें वह अधिकतम रकम ढूंढनी है जो चोर आज रात बिना पुलिस को अलर्ट किए चुरा सकता है। यदि ट्री इस प्रकार है -
तो आउटपुट 7 होगा।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -
- solve() नामक एक मेथड परिभाषित करें, यह नोड लेगा
- यदि नोड null है, तो एक पेयर (-इन्फिनिटी, 0) लौटाएं
- लेफ्टवैल := नोड का लेफ्ट, राइटवैल := नोड का राइट
- लेफ्टवैल का फर्स्ट एलिमेंट := लेफ्टवैल के फर्स्ट एलिमेंट और 0 का मैक्स
- लेफ्टवैल का सेकंड एलिमेंट := लेफ्टवैल के सेकंड एलिमेंट और 0 का मैक्स
- राइटवैल का फर्स्ट एलिमेंट := राइटवैल के फर्स्ट एलिमेंट और 0 का मैक्स
- राइटवैल का सेकंड एलिमेंट := राइटवैल के सेकंड एलिमेंट और 0 का मैक्स
- करंटवैल := नोड के मान और 0 का मैक्स
- कैंटबीएडेड := करंटवैल + लेफ्टवैल का सेकंड मान + राइटवैल का सेकंड मान
- कैनबीएडेड := (लेफ्टवैल का फर्स्ट मान + राइटवैल का फर्स्ट मान) का मैक्स और (लेफ्टवैल का सेकंड मान, राइटवैल का सेकंड मान, लेफ्टवैल का सेकंड मान + राइटवैल का सेकंड मान, लेफ्टवैल का सेकंड मान + राइटवैल का फर्स्ट मान, राइटवैल का सेकंड मान + लेफ्टवैल का फर्स्ट मान) का मैक्स
- एक पेयर लौटाएं (कैंटबीएडेड, कैनबीएडेड)
- मेन मेथड में, a := solve(रूट) बनाएं, फिर a के फर्स्ट मान और सेकंड मान का मैक्स लौटाएं।
उदाहरण (C++)
बेहतर समझ के लिए निम्नलिखित इम्प्लीमेंटेशन देखें -
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = right = NULL; } }; void insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; } else{ q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; } else { q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } const int INF = -1e8; class Solution { public: void printData(pair <int,int> t){ cout << t.first << " " << t.second << endl; } pair <int,int> solve(TreeNode* node){ if(!node){ return {INF,0}; } pair <int,int> leftVal = solve(node->left); pair <int,int> rightVal = solve(node->right); leftVal.first = max(leftVal.first,0); leftVal.second = max(leftVal.second,0); rightVal.second = max(rightVal.second,0); rightVal.first = max(rightVal.first,0); int currentVal = max(node->val,0); int cantBeAdded = currentVal + leftVal.second + rightVal.second; int canBeAdded =max(leftVal.first + rightVal.first,max({ leftVal.second,rightVal.second,leftVal.second + rightVal.second,leftVal.second+rightVal.first,rightVal.second+leftVal.first })); return {cantBeAdded,canBeAdded}; } int rob(TreeNode* root) { pair <int,int> a = solve(root); return max(a.first,a.second); } }; main(){ Solution ob; vector<int> v = {3,2,3,NULL,3,NULL,1}; TreeNode *root = make_tree(v); cout << (ob.rob(root)); }इनपुट
[3,2,3,null,3,null,1]
आउटपुट
7
