ধরি একটি বাইনারি ট্রির রুট (root) দেওয়া আছে। আমাদের সেই ট্রির যেকোনো সাবট্রি (subtree) যা একটি বাইনারি সার্চ ট্রি (BST), তার সব নোডের যোগফলের সর্বোচ্চ মান বের করতে হবে।
ইনপুট যদি হয় –
তাহলে আউটপুট হবে 20, কারণ নির্বাচিত BST-এর সব নোডের যোগফল 20।
সমাধানের ধাপসমূহ
Data নামক একটি স্ট্রাকচার তৈরি করুন, যাতে sz, maxVal, minVal, ok, sum 멤্বার থাকবে। এছাড়াও Data-এর একটি ইনিশিয়ালাইজার সংজ্ঞায়িত করুন যা (sz, minVal, maxVal, ok) নেবে এবং sum 0 সেট করবে।
ret := 0
solve() নামে একটি মেথড সংজ্ঞায়িত করুন, যা ট্রি রুট নেবে।
যদি node নন-জিরো না হয় বা node-এর ভ্যালু 0 হয়, তবে –
(0, inf, -inf, true) দিয়ে ইনিশিয়ালাইজ করা একটি নতুন Data ফেরত দিন
left := solve(node-এর left)
right := solve(node-এর right)
curr নামক একটি Data টাইপের ইন্সট্যান্স তৈরি করুন
curr.ok := false
যদি node->val >= right.minVal হয়, তবে –
curr ফেরত দিন
যদি node->val <= left.maxVal হয়, তবে –
curr ফেরত দিন
যদি left.ok এবং right.ok উভয়ই নন-জিরো হয়, তবে –
curr.sum := node->val + left.sum + right.sum
ret := max(curr.sum, ret)
curr.sz := 1 + left.sz + right.sz
curr.ok := true
curr.maxVal := max(node->val, right.maxVal)
curr.minVal := min(node->val, left.minVal)
curr ফেরত দিন
মূল পদ্ধতিতে –
ret := 0
solve(root) কল করুন
ret ফেরত দিন
বेहतर বোঝার জন্য নিচের কোডটি দেখুন –
উদাহরণ
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = NULL; 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; } struct Data{ int sz; int maxVal; int minVal; bool ok; int sum; Data(){} Data(int a, int b, int c, bool d){ sz = a; minVal = b; maxVal = c; ok = d; sum = 0; } }; class Solution { public: int ret = 0; Data solve(TreeNode* node){ if (!node || node->val == 0) return Data(0, INT_MAX, INT_MIN, true); Data left = solve(node->left); Data right = solve(node->right); Data curr; curr.ok = false; if (node->val >= right.minVal) { return curr; } if (node->val <= left.maxVal) { return curr; } if (left.ok && right.ok) { curr.sum = node->val + left.sum + right.sum; ret = max(curr.sum, ret); curr.sz = 1 + left.sz + right.sz; curr.ok = true; curr.maxVal = max(node->val, right.maxVal); curr.minVal = min(node->val, left.minVal); } return curr; } int maxSumBST(TreeNode* root){ ret = 0; solve(root); return ret; } }; main(){ Solution ob; vector<int> v = {1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6}; TreeNode *root = make_tree(v); cout << (ob.maxSumBST(root)); }ইনপুট
{1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6}আউটপুট
20
