मान लीजिए कि हमारे पास अलग-अलग मूल्यों के साथ एक बाइनरी सर्च ट्री की जड़ है, हमें इसे संशोधित करना होगा ताकि प्रत्येक नोड का मूल पेड़ के मूल्यों के योग के बराबर एक नया मान हो जो नोड के मूल्य से अधिक या उसके बराबर हो। हमें यह ध्यान रखना होगा कि हम बाइनरी सर्च ट्री के साथ काम कर रहे हैं, और यह बीएसटी के गुणों को बनाए रखना चाहिए। तो अगर इनपुट ट्री जैसा है -
तब आउटपुट ट्री होगा -
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
वैश्विक सेट करें:=0
-
एक पुनरावर्ती फ़ंक्शन हल () को परिभाषित करें, जो इनपुट के रूप में रूट लेगा।
-
यदि मूल का दायाँ अशक्त नहीं है, तो हल करें(मूल का दायाँ)
-
वैश्विक:=वैश्विक + जड़ का मूल्य
-
यदि रूट का बायां भाग शून्य नहीं है, तो हल करें (रूट के बाएं)
-
वापसी जड़
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#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, ]