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

तो आउटपुट 5 होगा। सबसे छोटा मान 2 है, दूसरा सबसे छोटा मान 5 है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
- एक फ़ंक्शन
TraverseNodes()परिभाषित करें, जोnode, min, nextMinलेगा,- यदि
nodenull है, तो वापस लौटें - यदि
node का मान > min, तो:- यदि
nextMin == -1याnode का मान < nextMin, तो:nextMin := node का मान
- यदि
TraverseNodes(node का बायां, min, nextMin)TraverseNodes(node का दायां, min, nextMin)
- यदि
- मुख्य विधि से निम्नलिखित करें:
min := root का मान यदि root null नहीं है, अन्यथा -1nextMin := -1TraverseNodes(root, min, nextMin)nextMinवापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
उदाहरण
#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);
}
};
int 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