ধরুন আমাদের কাছে স্বতন্ত্র মান সহ একটি বাইনারি অনুসন্ধান গাছের মূল রয়েছে, আমাদের এটিকে সংশোধন করতে হবে যাতে প্রতিটি নোডের মূল গাছের মানের সমষ্টির সমান একটি নতুন মান থাকে যা নোডের মানের চেয়ে বড় বা সমান। আমাদের মনে রাখতে হবে যে আমরা বাইনারি সার্চ ট্রি নিয়ে কাজ করছি এবং এটি BST-এর বৈশিষ্ট্য বজায় রাখতে হবে। তাই যদি ইনপুট ট্রি −
এর মত হয়
তারপর আউটপুট ট্রি হবে −
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
সেট গ্লোবাল :=0
-
একটি পুনরাবৃত্ত ফাংশন সংজ্ঞায়িত করুন solve(), যা ইনপুট হিসাবে রুট করবে।
-
যদি মূলের ডানদিকে শূন্য না হয়, তাহলে সমাধান করুন(মূলের ডানদিকে)
-
global :=গ্লোবাল + রুটের মান
-
যদি মূলের বাম অংশটি শূন্য না হয়, তাহলে সমাধান করুন(মূলের বামে)
-
রিটার্ন রুট
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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;
}
void tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue<TreeNode *> q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
}
else {
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr == NULL || curr->val == 0){
cout << "null" << ", ";
}else{
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
int global = 0;
TreeNode* bstToGst(TreeNode* root) {
if(root->right)bstToGst(root->right);
if(root->val != 0)
root->val = global = global + root->val;
if(root->left)bstToGst(root->left);
return root;
}
};
main(){
vector<int> v =
{4,1,6,1,2,5,7,NULL,NULL,NULL,3,NULL,NULL,NULL,8};
TreeNode *root = make_tree(v);
Solution ob;
tree_level_trav(ob.bstToGst(root));
} ইনপুট
[4,1,6,1,2,5,7,null,null,null,3,null,null,null,8]
আউটপুট
[30, 36, 21, 37, 35, 26, 15, null, null, null, 33, null, null, null, 8, ]
