C++-এ হাউস রবার III

মনে করুন একজন চোর তার চুরির জন্য নতুন একটি জায়গা পেয়েছে। এই এলাকায় শুধু একটি এন্ট্রেন্স আছে, যাকে "রুট" বলা হয়। রুট ছাড়া প্রতিটি ঘরের এক এবং শুধু এক পেরেন্ট ঘর আছে। একবার ঘুরে বেড়ানোর পর স্মার্ট চোর বুঝতে পারলো যে "এই এলাকায় সব ঘর একটি বাইনারি ট্রি বানালো"। এবং যদি একই রাতে দুটি সরাসরি লিংক করা ঘরে চুরি করা হয়, তবে এটি অটোমেটিক্যালি পুলিশকে খবর দেবে। আমাদের চোর আজ রাতে পুলিশকে খবর দিয়ে ছাড়া চুরি করতে পারবে সর্বোচ্চ কত টাকা তা বের করতে হবে। যদি ট্রি নিচের মোতাবিক হয় -

C++-এ হাউস রবার III

তবে আউটপুট হবে ৭।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

`solve()` নামক একটি মেথড সংজ্ঞায়িত করুন, এটি `node` নেবে
যদি `node` null হয়, তবে একটি পেয়ার `(-infinity, 0)` রিটার্ন করুন
`leftVal := node`-এর বাম, `rightVal := node`-এর ডান
`leftVal`-এর ফাস্ট এলিমেন্ট := `leftVal`-এর ফাস্ট এবং ০-এর ম্যাক্স
`leftVal`-এর সেকেন্ড এলিমেন্ট := `leftVal`-এর সেকেন্ড এবং ০-এর ম্যাক্স
`rightVal`-এর ফাস্ট এলিমেন্ট := `rightVal`-এর ফাস্ট এবং ০-এর ম্যাক্স
`rightVal`-এর সেকেন্ড এলিমেন্ট := `rightVal`-এর সেকেন্ড এবং ০-এর ম্যাক্স
`currVal := node`-এর মান এবং ০-এর ম্যাক্স
`cantBeAdded := currVal + leftVal`-এর সেকেন্ড + `rightVal`-এর সেকেন্ড
`canBeAdded :=` max of (`leftVal.first + rightVal.first`) এবং max of (`leftVal.second`, `rightVal.second`, `leftVal.second + rightVal.second`, `leftVal.second + rightVal.first`, `rightVal.second + leftVal.first`)
একটি পেয়ার `(cantBeAdded, canBeAdded)` রিটার্ন করুন
মেইন মেথডে, `a := solve(root)` করুন, তারপর `max(a.first, a.second)` রিটার্ন করুন।

উদাহরণ (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]