C++ में बाइनरी सर्च ट्री को ग्रेटर सम ट्री में बदलें

मान लीजिए हमारे पास अलग-अलग मानों वाले बाइनरी सर्च ट्री की रूट है, हमें इसे संशोधित करना होगा ताकि प्रत्येक नोड का नया मान मूल ट्री के उन मानों के योग के बराबर हो जो नोड के मान से बड़े या बराबर हैं। हमें ध्यान रखना होगा कि हम बाइनरी सर्च ट्री के साथ काम कर रहे हैं, और यह BST के गुणों को बनाए रखना चाहिए।

इसलिए यदि इनपुट ट्री इस तरह है:

तो आउटपुट ट्री इस तरह होगा:

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• global := 0 सेट करें

• एक रिकर्सिव फ़ंक्शन solve() परिभाषित करें, जो रूट को इनपुट के रूप में लेगा।

• यदि रूट का राइट null नहीं है, तो solve(रूट का राइट)

• global := global + रूट का मान

• यदि रूट का लेफ्ट null नहीं है, तो solve(रूट का लेफ्ट)

• रूट लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

#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;
    }
};

int 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, ]