C++-এ Binary Search Tree to Greater Sum Tree

ধরি আমাদের একটি বাইনারি সার্চ ট্রির রুট আছে যাতে ডিস্টিংক্ট ভ্যালু আছে, আমাদের এটিকে মডিফাই করতে হবে যাতে প্রতিটি নোডের একটি নতুন ভ্যালু থাকে যা ওরিজিনাল ট্রির那些 ভ্যালুগুলোর সমান যা নোডের ভ্যালু থেকে বড় বা সমান। আমাদের মনে রাখতে হবে যে আমরা বাইনারি সার্চ ট্রি নিয়ে কাজ করছি, এবং এটি BST-এর প্রোপার্টি মেইনটেইন করতে হবে। ইনপুট ট্রি যদি নিচের মত হয়:

তবে আউটপুট ট্রি হবে:

এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:

• global := 0 সেট করুন

• একটি রিকার্সিভ ফাংশন solve() ডিফাইন করুন, যা root ইনপুট হিসেবে নিবে।

• যদি root-এর right null না হয়, তবে solve(right of root)

• global := global + value of root

• যদি root-এর left null না হয়, তবে solve(left of root)

• root রিটার্ন করুন

নিচের ইমপ্লিমেন্টেশনটি দেখুন ভালো বোঝার জন্য:

উদাহরণ

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