C++ में हाउस रॉबर III

मान लीजिए कि एक चोर ने अपनी चोरी के लिए फिर से एक नई जगह ढूंढ ली है। इस क्षेत्र में केवल एक प्रवेश द्वार है, प्रवेश द्वार को "रूट" कहा जाता है। जड़ के अलावा, प्रत्येक घर में एक और केवल एक मूल घर होता है। एक दौरे के बाद, स्मार्ट चोर को लगा कि "इस जगह के सभी घर एक बाइनरी ट्री बनाते हैं"। और अगर एक ही रात में दो सीधे जुड़े घरों को तोड़ा गया तो यह स्वचालित रूप से पुलिस से संपर्क करेगा। हमें यह पता लगाना है कि चोर आज रात पुलिस को सूचित किए बिना कितनी राशि लूट सकता है। तो अगर पेड़ जैसा है -

तब आउटपुट 7 होगा।

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

हल () नामक एक विधि को परिभाषित करें, यह नोड लेगा
यदि नोड शून्य है, तो एक जोड़ी लौटाएं (-इन्फिनिटी, 0)
बायां वैल:=नोड के बाएं, दाएं वैल:=नोड के दाएं
लेफ्टवैल का पहला एलिमेंट:=लेफ्टवैल के पहले एलिमेंट का अधिकतम और 0
लेफ्टवैल का दूसरा एलिमेंट:=लेफ्टवैल के दूसरे एलिमेंट का अधिकतम और 0
राइटवैल का पहला एलिमेंट:=राइटवैल के पहले एलिमेंट का अधिकतम और 0
राइटवैल का दूसरा तत्व:=राइटवैल के दूसरे तत्व का अधिकतम और 0
currVal :=नोड का अधिकतम मान और 0
cantBeAdded :=currVal + leftVal का दूसरा मान + rightVal का दूसरा मान
canBeAdded:=अधिकतम (बाएं वैल का पहला मान + दाएं वैल का पहला मान) और अधिकतम (बाएं वैल का दूसरा मान, दाएं वैल का दूसरा मान, बाएं वैल का दूसरा मान + दाएं वैल का दूसरा मान, बाएं वैल का दूसरा मान + दाएं वैल का पहला मान, राइटवैल का दूसरा मान + लेफ्टवैल का पहला मान)
एक जोड़ी लौटाएं (कैंटबीएडेड, कैनबीएडेड)
मुख्य विधि में, a :=हल करें (रूट), फिर a के पहले मान का अधिकतम और 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]