C++ এ প্রদত্ত মান সহ পাতা মুছুন

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

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• remLeaf() নামে একটি পুনরাবৃত্ত পদ্ধতি সংজ্ঞায়িত করুন, এটি রুট এবং লক্ষ্য গ্রহণ করবে

• যদি রুটটি শূন্য হয়, তাহলে শূন্য দিন

• left :=remLeaf(মূলের বামে, লক্ষ্য)

• ডানে :=remLeaf(মূলের ডানদিকে, লক্ষ্য)

• যদি বাম নাল হয় এবং ডান নাল হয় এবং রুটের মান টার্গেটের সমান হয়, তাহলে নাল রিটার্ন করুন

• মূলের বাম :=বাম

• মূলের অধিকার :=ডান

• রিটার্ন রুট

উদাহরণ (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;
      }
};
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, ]