C++ में BST को ग्रेटर ट्री में बदलें

समस्या विवरण

मान लीजिए हमारे पास एक बाइनरी सर्च ट्री (BST) है, हमें इसे एक ग्रेटर ट्री में बदलना है ताकि मूल BST की प्रत्येक कुंजी को मूल कुंजी + BST में मूल कुंजी से बड़ी सभी कुंजियों के योग में बदल दिया जाए।

उदाहरण

यदि इनपुट ट्री है:

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

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (रिवर्स इनऑर्डर ट्रैवर्सल):

• revInorder() नामक एक फ़ंक्शन परिभाषित करें, जो ट्री रूट और s लेता है
• यदि रूट null है, तो लौटें
• revInorder(रूट का राइट, s)
• s := s + रूट का मान
• रूट का मान := s
• revInorder(रूट का लेफ्ट, s)
• मुख्य विधि से:
  • यदि रूट null है, तो null लौटाएं
  • sum := 0
  • revInorder(रूट, sum)
  • रूट लौटाएं

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;
    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:
    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, ]