C++ में बाइनरी ट्री की न्यूनतम गहराई

मान लीजिए हमारे पास एक बाइनरी ट्री है; हमें उस वृक्ष की न्यूनतम गहराई ज्ञात करनी है। जैसा कि हम जानते हैं कि न्यूनतम गहराई रूट नोड से निकटतम लीफ नोड तक सबसे छोटे पथ के साथ नोड्स की संख्या है।

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

तो आउटपुट 2

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

• ट्री नोड्स की सरणी आ परिभाषित करें

• आ के अंत में जड़ डालें

• ट्री नोड्स की एक और सरणी परिभाषित करें

• स्तर:=0

• यदि रूट शून्य है, तो -

  • वापसी 0

• जबकि आ का आकार 0 के बराबर नहीं है, करें -

  • सरणी को साफ़ करें ak

  • (स्तर 1 से बढ़ाएँ)

  • आ में सभी नोड के लिए -

    • अगर (एक का बायां शून्य है) और (एक का दायां शून्य है), तो -

      • वापसी स्तर

      • लूप से बाहर आएं

    • यदि a का बायां भाग शून्य नहीं है, तो -

      • ak के अंत में a के बाईं ओर डालें

    • यदि a का दायाँ अशक्त नहीं है, तो -

      • ak के अंत में a के दाईं ओर डालें

  • आ:=एके

• वापसी 0

उदाहरण

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

#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 minDepth(TreeNode* root) {
      vector<TreeNode*> aa;
      aa.push_back(root);
      vector<TreeNode*> ak;
      int level = 0;
      if (root == NULL || root->val == 0) {
         return 0;
      }
      while (aa.size() != 0) {
         ak.clear();
         level++;
         for (TreeNode* a : aa) {
            if ((a->left == NULL || a->left->val == 0)&& (a->right == NULL || a->right->val == 0)) {
               return level;
               break;
            }
            if (a->left != NULL) {
               ak.push_back(a->left);
            }
            if (a->right != NULL) {
               ak.push_back(a->right);
            }
         }
         aa = ak;
      }
      return 0;
   }
};
main(){
   Solution ob;
   vector<int&g; v = {3,9,20,NULL,NULL,15,7};
   TreeNode *root = make_tree(v);
   cout << (ob.minDepth(root));
}

इनपुट

{3,9,20,NULL,NULL,15,7}

आउटपुट

2