C++ में सभी गहरे नोड्स के साथ सबसे छोटा सबट्री

मान लीजिए कि हमारे पास एक बाइनरी ट्री है जिसकी जड़ें जड़ में हैं, प्रत्येक नोड की गहराई जड़ से सबसे छोटी दूरी है। यहां एक नोड सबसे गहरा है यदि पूरे पेड़ में किसी भी नोड के बीच इसकी सबसे बड़ी गहराई संभव है। एक नोड का उपप्रकार वह नोड है, साथ ही उस नोड के सभी वंशजों का समूह। हमें नोड को सबसे बड़ी गहराई के साथ खोजना होगा जैसे कि इसके सबट्री में सभी गहरे नोड्स शामिल हों। तो अगर पेड़ जैसा है -

तब सबसे गहरा सबट्री होगा -

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

• हल () नामक एक विधि को परिभाषित करें, यह इनपुट के रूप में जड़ लेगा

• यदि रूट शून्य है, तो वापस लौटें (शून्य, 0)

• एल:=हल करें (रूट के बाएं), आर:=हल करें (रूट के दाएं)

• यदि बाएँ का दूसरा मान> r का दूसरा मान है, तो एक जोड़ी लौटाएँ (l का पहला, l का 1 + सेकंड)

• अन्यथा जब बाएँ का दूसरा मान

• एक जोड़ी लौटाएं(रूट, एल + 1 का दूसरा)

• मुख्य विधि से हल (रूट) को कॉल करें, और इसका दूसरा मान लौटाएं

उदाहरण(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:
   pair <TreeNode*, int> solve(TreeNode* root){
      if(!root || root->val == 0) return {NULL, 0};
      pair <TreeNode*, int> L = solve(root->left);
      pair <TreeNode*, int> R = solve(root->right);
      if(L.second > R.second)return {L.first, L.second + 1};
      else if(L.second < R.second) return {R.first, R.second + 1};
      return {root, L.second + 1};
   }
   TreeNode* subtreeWithAllDeepest(TreeNode* root) {
      return solve(root).first;
   }
};
main(){
   vector<int> v = {3,5,1,6,2,0,8,NULL,NULL,7,4};
   TreeNode *root = make_tree(v);
   Solution ob;
   tree_level_trav(ob.subtreeWithAllDeepest(root)) ;
}

इनपुट

{3,5,1,6,2,0,8,NULL,NULL,7,4}

आउटपुट

[2,7,4]