C++ में एक बाइनरी ट्री में दूसरा न्यूनतम नोड

मान लीजिए कि कुछ गैर-नकारात्मक मान वाला एक गैर-खाली विशेष बाइनरी ट्री है, यहाँ इस पेड़ के प्रत्येक नोड में ठीक दो या शून्य बच्चे हैं। यदि नोड के दो बच्चे हैं, तो इस नोड का मान उसके दो बच्चों के बीच छोटा मान है। दूसरे शब्दों में, हम कह सकते हैं कि [root.val =न्यूनतम root.left.val, root.right.val]। यदि हमारे पास ऐसा बाइनरी ट्री है, तो हमें पूरे ट्री में सभी नोड्स के मान से बने सेट में दूसरा न्यूनतम मान खोजना होगा। अगर ऐसा कोई तत्व नहीं है, तो इसके बजाय -1 लौटाएं।

तो, अगर इनपुट पसंद है

तो आउटपुट 5 होगा। सबसे छोटा मान 2 है, दूसरा सबसे छोटा मान 5 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

एक फ़ंक्शन को परिभाषित करें TraverseNodes(), इसमें नोड, मिनट, अगला मिनट लगेगा,
यदि नोड शून्य है, तो −
- वापसी
यदि नोड का मान> मिनट है, तो −
- यदि अगलामिन -1 या नोड के वैल <नेक्स्टमिन के समान है, तो -
  - अगला मिनट :=नोड का मान
TraverseNodes (नोड के बाएँ, min, nextMin)
TraverseNodes (नोड के दाईं ओर, मिनट, अगला मिनट)
मुख्य विधि से निम्न कार्य करें -
मिनट :=रूट का मान जब रूट शून्य न हो, अन्यथा -1
अगले मिनट :=-1
ट्रैवर्सनोड्स (रूट, मिन, नेक्स्टमिन)
अगले मिनट पर लौटें

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#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}