ধরা যাক একটি N-ary ট্রি আছে, আমরা এর নোডদের মান লেভেল অর্ডার ট্রাভার্সাল হিসেবে রিটার্ন করব। N-ary ট্রি ইনপুট সিরিয়ালাইজেশন তাদের লেভেল অর্ডার ট্রাভার্সাল হিসেবে রিপ্রেজেন্ট করা হয়। এখানে প্রতিটি চাইল্ড গ্রুপ null ভ্যালু দিয়ে পৃথক করা হয় (উদাহরণ দেখুন)। নিচের ট্রিটি নিচের মতো রিপ্রেজেন্ট করা যেতে পারে [1,null,3,2,4,null,5,6]
আউটপুট হবে [[1],[3,2,4],[5,6]]
সমাধানের ধাপগুলো −
ans নামে একটি ম্যাট্রিক্স বানাব
যদি রুট null হয়, তবে ans রিটার্ন করব
একটি কিউ q বানিয়ে রুট ইনসার্ট করব
যখন q খালি নয়
size := কিউর আকার
temp নামক একটি অ্যারে বানাব
যখন size ০ নয়
curr := q-এর প্রথম এলিমেন্ট
curr-এর মান temp-এ ইনসার্ট করব
কিউ থেকে এলিমেন্ট ডিলিট করব
i = 0 থেকে curr-এর চাইল্ডদের আকার পর্যন্ত
curr-এর i-তম চাইল্ড ইনসার্ট করব
size ১ কমানো
temp ans-এ ইনসার্ট করব
ans রিটার্ন করব
নিচের ইমপ্লিমেন্টেশন দেখুন −
উদাহরণ
#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, ],]
