C++ এ একটি বাইনারি ট্রিতে দ্বিতীয় সর্বনিম্ন নোড

ধরুন কিছু অ-নেতিবাচক মান সহ একটি খালি বিশেষ বাইনারি গাছ আছে, এখানে এই গাছের প্রতিটি নোডে ঠিক দুটি বা শূন্য সন্তান রয়েছে। যদি নোডের দুটি সন্তান থাকে, তাহলে এই নোডের মানটি তার দুটি সন্তানের মধ্যে ছোট মান। অন্য কথায়, আমরা বলতে পারি যে [root.val =minimum of root.left.val, root.right.val]। আমাদের যদি এমন বাইনারি ট্রি থাকে, তাহলে পুরো গাছের সমস্ত নোডের মান দিয়ে তৈরি সেটে আমাদের দ্বিতীয় সর্বনিম্ন মান খুঁজে বের করতে হবে। যদি এমন কোনো উপাদান না থাকে, তাহলে এর পরিবর্তে -1 রিটার্ন করুন।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 5। ক্ষুদ্রতম মান হল 2, দ্বিতীয় ক্ষুদ্রতম মান হল 5।

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

• একটি ফাংশন সংজ্ঞায়িত করুন TraverseNodes(), এটি নোড, মিন, নেক্সটমিন,
• যদি নোডটি শূন্য হয়, তাহলে −
  • প্রত্যাবর্তন
• নোডের val> min হলে −
  • যদি nextMin হয় -1 বা নোডের val
  • nextMin :=নোডের val

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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;
}
class Solution {
public:
   int findSecondMinimumValue(TreeNode* root) {
      int min = (root && root->val != 0) ? root->val : -1;
      int nextMin = -1;
      TraverseNodes(root, min, nextMin);
      return nextMin;
   }
   void TraverseNodes(TreeNode* node, int min, int& nextMin) {
      if (!node || node->val == 0) {
         return;
      }
      if (node->val > min) {
         if (nextMin == -1 || node->val < nextMin) {
            nextMin = node->val;
         }
      }
      TraverseNodes(node->left, min, nextMin);
      TraverseNodes(node->right, min, nextMin);
   }
};
main(){
   Solution ob;
   vector<int> v = {2,2,5,NULL,NULL,5,7};
   TreeNode *root = make_tree(v);
   cout << (ob.findSecondMinimumValue(root));
}

ইনপুট

{2,2,5,NULL,NULL,5,7}

আউটপুট

5