একটি বাইনারি সার্চ ট্রি (BST) দেওয়া আছে। এটি একটি গ্রেটার ট্রিতে রূপান্তর করতে হবে যাতে প্রতিটি নোডের মান = মূল মান + BST-এ সেই নোড থেকে বড় সব নোডের মান যোগফল।
উদাহরণস্বরূপ, ইনপুট ট্রি:
আউটপুট ট্রি:
সমাধানের ধাপসমূহ
- revInorder() ফাংশন সংজ্ঞায়িত করুন যা রুট এবং সামরিক sum নেয়।
- যদি রুট null হয়, ফেরত যান।
- revInorder(রুট->ডান, sum) কল করুন।
- sum := sum + রুট->val।
- রুট->val := sum।
- revInorder(রুট->বাম, sum) কল করুন।
- মূল ফাংশনে: যদি রুট null হয়, null রিটার্ন করুন। sum=0 দিয়ে revInorder কল করুন। রুট রিটার্ন করুন।
C++ কোড উদাহরণ
#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;
q.push(root); q.push(NULL);
while (q.size() > 1) {
TreeNode *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:
void revInorder(TreeNode *root, int &s) {
if (root == NULL || root->val == 0) return;
revInorder(root->right, s);
s += root->val;
root->val = s;
revInorder(root->left, s);
}
TreeNode* convertBST(TreeNode* root) {
if (root == NULL || root->val == 0) return NULL;
int sum = 0;
revInorder(root, sum);
return root;
}
};
int main() {
Solution ob;
vector<int> v = {5,2,8,NULL,NULL,6,9};
TreeNode *root = make_tree(v);
tree_level_trav(ob.convertBST(root));
return 0;
}
ইনপুট
{5,2,8,NULL,NULL,6,9}
আউটপুট
[28, 30, 17, null, null, 23, 9, ]
