ধরুন একজন চোর আবার তার চোরের জন্য একটি নতুন জায়গা খুঁজে পেয়েছে৷ এই এলাকায় একটি মাত্র প্রবেশদ্বার আছে, প্রবেশদ্বারটিকে "মূল" বলা হয়। মূল ছাড়াও, প্রতিটি বাড়িতে একটি এবং শুধুমাত্র একটি পিতামাতার বাড়ি রয়েছে। একটি সফরের পরে, বুদ্ধিমান চোরটি অনুভব করেছিল যে "এই জায়গার সমস্ত বাড়ি একটি বাইনারি গাছ তৈরি করে"। এবং একই রাতে দুটি সরাসরি-সংযুক্ত বাড়িতে ভাঙা হলে এটি স্বয়ংক্রিয়ভাবে পুলিশের সাথে যোগাযোগ করবে। পুলিশকে সতর্ক না করেই আজ রাতে চোর সর্বোচ্চ কত টাকা ছিনতাই করতে পারে তা আমাদের খুঁজে বের করতে হবে। তাই গাছটি যদি −
এর মত হয়
তাহলে আউটপুট হবে 7.
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
সমাধান() নামক একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি নোড গ্রহণ করবে
-
যদি নোড শূন্য হয়, তাহলে একটি জোড়া (-ইনফিনিটি, 0)
ফেরত দিন -
leftVal :=নোডের বাম, rightVal :=নোডের ডান
-
LeftVal এর প্রথম এলিমেন্ট :=LeftVal এর প্রথম এলিমেন্টের সর্বোচ্চ এবং 0
-
LeftVal-এর দ্বিতীয় উপাদান :=leftVal-এর দ্বিতীয় উপাদানের সর্বোচ্চ এবং 0
-
rightVal এর প্রথম উপাদান :=rightVal এবং 0
এর প্রথম উপাদানের সর্বোচ্চ -
rightVal এর দ্বিতীয় উপাদান :=rightVal এর দ্বিতীয় উপাদানের সর্বোচ্চ এবং 0
-
currVal :=নোডের মানের সর্বোচ্চ এবং 0
-
cantBeAdded :=currVal + leftVal এর দ্বিতীয় মান + rightVal এর দ্বিতীয় মান
-
canBeAdded :=সর্বাধিক (leftVal-এর প্রথম মান + rightVal-এর প্রথম মান) এবং সর্বাধিক (leftVal-এর দ্বিতীয় মান, rightVal-এর দ্বিতীয় মান, leftVal-এর দ্বিতীয় মান + rightVal-এর দ্বিতীয় মান, leftVal-এর দ্বিতীয় মান + rightVal-এর প্রথম মান, rightVal-এর দ্বিতীয় মান + leftVal-এর প্রথম মান)
-
একটি জোড়া ফেরত দিন (ক্যান্টবিএডেড, ক্যানবিএডেড)
-
মূল পদ্ধতিতে, a :=solve(root) করুন, তারপর 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]
আউটপুট
7
