सी++ में एन-आरी ट्री लेवल ऑर्डर ट्रैवर्सल

मान लीजिए कि हमारे पास एक n-ary ट्री है, हमें इसके नोड्स के मानों के लेवल ऑर्डर ट्रैवर्सल को वापस करना होगा। नैरी-ट्री इनपुट क्रमांकन उनके स्तर के क्रम ट्रैवर्सल में दर्शाया गया है। यहां बच्चों के प्रत्येक समूह को शून्य मान से अलग किया जाता है (उदाहरण देखें)। तो निम्नलिखित पेड़ को [1,null,3,2,4,null,5,6]

आउटपुट होगा [[1],[3,2,4],[5,6]]

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

• एक मैट्रिक्स बनाओ ans

• यदि रूट शून्य है, तो उत्तर दें

• एक कतार q बनाएं और रूट डालें

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

  • आकार :=कतार का आकार

  • एक सरणी अस्थायी बनाएं

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

    • curr :=q का पहला तत्व

    • अस्थायी में curr का मान डालें

    • कतार से तत्व हटाएं

    • मेरे लिए 0 से लेकर कर्व के बच्चों के आकार तक

      • कर्व के बच्चों को सम्मिलित करें

    • आकार को 1 से कम करें

  • उत्तर में अस्थायी डालें

• वापसी उत्तर

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

उदाहरण

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Node {
   public:
   int val;
   vector<Node*> children;
   Node() {}
   Node(int _val) {
      val = _val;
   }
   Node(int _val, vector<Node*> _children) {
      val = _val;
      children = _children;
   }
};
class Solution {
   public:
   vector<vector<int>> levelOrder(Node* root) {
      vector < vector <int> > ans;
      if(!root)return ans;
         queue <Node*> q;
      q.push(root);
      while(!q.empty()){
         int sz = q.size();
         vector<int> temp;
         while(sz--){
            Node* curr = q.front();
            temp.push_back(curr->val);
            q.pop();
            for(int i = 0; i < curr->children.size(); i++){
               q.push(curr->children[i]);
            }
         }
         ans.push_back(temp);
      }
      return ans;
   }
};
main(){
   Node *root = new Node(1);
   Node *left_ch = new Node(3), *mid_ch = new Node(2), *right_ch = new Node(4);
   left_ch->children.push_back(new Node(5));
   left_ch->children.push_back(new Node(6));
   root->children.push_back(left_ch);
   root->children.push_back(mid_ch);
   root->children.push_back(right_ch);
   Solution ob;
   print_vector(ob.levelOrder(root));
}

इनपुट

[1,null,3,2,4,null,5,6]

आउटपुट

[[1, ],[3, 2, 4, ],[5, 6, ],]