C++-এ নির্দিষ্ট মান সহ লিফ নোড মুছুন

আমাদের কাছে একটি বাইনারি ট্রি এবং একটি ইন্টিজার target আছে, আমাদেরকে মান target সহ সমস্ত লিফ নোড মুছে ফেলতে হবে। মনে রাখবেন, একবার একটি লিফ নোড মুছে ফেললে, যদি তার পেরেন্ট নোড লিফ নোড হয়ে যায় এবং এর মান target হয়, তবে সেটিও মুছে ফেলতে হবে (এই প্রক্রিয়াটি চলতে থাকবে যতক্ষণ না করা যায় না)। উদাহরণস্বরূপ, যদি ট্রিটি নিচের ছবির মতো হয় এবং target ২ হয়, তবে চূড়ান্ত ট্রিটি শেষ ছবির মতো হবে -

সমাধানের ধাপসমূহ

• remLeaf() নামে একটি রিকার্সিভ মেথড সংজ্ঞায়িত করুন, যা রুট এবং টার্গেট গ্রহণ করবে।
• যদি রুট null হয়, তবে null রিটার্ন করুন।
• left := remLeaf(left of root, target)
• right := remLeaf(right of root, target)
• যদি left null হয় এবং right null হয় এবং রুটের মান টার্গেটের সমান হয়, তবে null রিটার্ন করুন।
• left of root := left
• right of root := right
• root রিটার্ন করুন।

উদাহরণ (C++)

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

#include <bits/stdc++.h>
using namespace std;

class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = 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->val == 0 || curr == NULL){
                cout << "null" << ", ";
            } else {
                cout << curr->val << ", ";
            }
        }
    }
    cout << "]"<<endl;
}

class Solution {
public:
    TreeNode* removeLeafNodes(TreeNode* root, int target) {
        if(!root || root->val == 0) return NULL;
        TreeNode* left = removeLeafNodes(root->left, target);
        TreeNode* right = removeLeafNodes(root->right, target);
        if(!left && !right && root->val == target){
            return NULL;
        }
        root->left = left;
        root->right = right;
        return root;
    }
};

int main() {
    vector<int> v1 = {1,2,3,2,NULL,2,4};
    TreeNode *root = make_tree(v1);
    Solution ob;
    tree_level_trav(ob.removeLeafNodes(root, 2));
}

ইনপুট

[1,2,3,2,null,2,4] 2

আউটপুট

[1, 3, 4, ]