C++ में बाइनरी ट्री की अधिकतम चौड़ाई

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, हमें दिए गए ट्री की अधिकतम चौड़ाई प्राप्त करने के लिए एक फ़ंक्शन को परिभाषित करना होगा। यहां एक पेड़ की चौड़ाई सभी स्तरों के बीच अधिकतम चौड़ाई है। हम विचार करेंगे कि बाइनरी ट्री में पूर्ण बाइनरी ट्री के समान संरचना होती है, लेकिन कुछ नोड शून्य होते हैं। एक स्तर की चौड़ाई वास्तव में अंत-नोड्स के बीच की लंबाई है (स्तर में सबसे बाएं और दाएं सबसे गैर-शून्य नोड्स, जहां अंत-नोड्स के बीच शून्य नोड्स को लंबाई गणना के लिए भी गिना जाता है)। तो अगर पेड़ जैसा है -

फिर अधिकतम चौड़ाई 4 है, क्योंकि अंतिम परत के नोड्स [5,3,null,9]

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

• उत्तर:=1, आकार:=0

• एक डबल एंडेड क्यू को परिभाषित करें जहां हम (नोड, वैल्यू) पेयर स्टोर करेंगे।

• q में (रूट, 1) डालें

• जबकि q खाली नहीं है

  • आकार :=क्यू का आकार

  • एक (नोड, मान) जोड़ी वक्र परिभाषित करें

  • यदि आकार 1 है, तो (सामने वाले तत्व का नोड, 1) q में, q से तत्व हटाएं

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

    • curr :=q का अगला तत्व, q से सामने वाले तत्व को हटा दें

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

      • बनाएँ (वर्तमान नोड के बाएँ, 2*कर्र का मान) और q में डालें

    • अगर कर्व नोड का अधिकार शून्य नहीं है, तो

      • बनाएं (वर्तमान नोड के दाईं ओर, 2 * कर्व + 1 का मान) और q में डालें

    • यदि q> 1 का आकार है, तो

      • उत्तर:=अधिकतम उत्तर, q में अंतिम तत्व का मान - q + 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 widthOfBinaryTree(TreeNode* root) {
      int ans = 0;
      deque < pair <TreeNode*, int> > q;
      q.push_back({root,1});
      ans = 1;
      int size;
      while(!q.empty()){
         size = q.size();
         pair <TreeNode*, int> curr;
         if(size == 1){
            q.push_back({q.front().first, 1});
            q.pop_front();
         }
         while(size--){
            curr = q.front();
            q.pop_front();
            if(curr.first->left){
               q.push_back({curr.first->left, 2 * curr.second});
            }
            if(curr.first->right){
               q.push_back({curr.first->right, 2 * curr.second + 1});
            }
         }
         if(q.size() > 1)
            ans = max(ans, q.back().second - q.front().second + 1);
      }
      return ans;
   }
};
main(){
   vector<int> v = {1,3,2,5,3,NULL,9};
   TreeNode *root = make_tree(v);
   Solution ob;
   cout << (ob.widthOfBinaryTree(root));
}

इनपुट

[1,3,2,5,3,null,9]

आउटपुट

4