C++-এ N-ary Tree Level Order Traversal

ধরুন আমাদের একটি n-ary গাছ আছে, আমাদেরকে এর নোডের মানগুলির লেভেল অর্ডার ট্রাভার্সাল ফেরত দিতে হবে। ন্যারি-ট্রি ইনপুট সিরিয়ালাইজেশন তাদের লেভেল অর্ডার ট্রাভার্সালে উপস্থাপন করা হয়। এখানে শিশুদের প্রতিটি গ্রুপ শূন্য মান দ্বারা পৃথক করা হয়েছে (উদাহরণ দেখুন)। সুতরাং নিম্নলিখিত গাছটিকে [1,null,3,2,4,null,5,6] হিসাবে উপস্থাপন করা যেতে পারে

আউটপুট হবে [[1],[3,2,4],[5,6]]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ম্যাট্রিক্স উত্তর তৈরি করুন

• রুট শূন্য হলে, উত্তর দিন

• একটি সারি q করুন এবং রুট সন্নিবেশ করুন

• যখন q খালি নয়

  • আকার :=সারির আকার

  • একটি অ্যারে টেম্প তৈরি করুন

  • যখন আকার 0

    নয়

    • curr :=q এর প্রথম উপাদান

    • temp

      এ curr এর মান সন্নিবেশ করান

    • সারি থেকে উপাদান মুছুন

    • আমার জন্য 0 থেকে curr-এর বাচ্চাদের আকার

      • সন্নিবেশ করান ith কার সন্তানদের

    • 1 দ্বারা আকার হ্রাস করুন

  • উত্তরে তাপমাত্রা সন্নিবেশ করান

• উত্তর ফেরত দিন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include  namespace ব্যবহার করে std;void print_vector(vector> v){ cout <<"["; for(int i =0; i শিশু; নোড() {} নোড(int _val) { val =_val; } নোড(int _val, ভেক্টর<নোড*> _children) { val =_val; শিশু =_শিশু; }};ক্লাস সলিউশন { পাবলিক:ভেক্টর<ভেক্টর> লেভেলঅর্ডার(নোড* রুট) { ভেক্টর <ভেক্টর > উত্তর; যদি(!root) উত্তর দেয়; সারি <নোড*> q; q. push(মূল); যখন(!q.empty()){ int sz =q.size(); ভেক্টর temp; while(sz--){ Node* curr =q.front(); temp.push_back(curr->val); q.pop(); for(int i =0; i children.size(); i++){ q.push(curr->children[i]); } } ans.push_back(temp); } উত্তর দিন; }};প্রধান(){নোড *রুট =নতুন নোড(1); নোড *left_ch =new Node(3), *mid_ch =new Node(2), *right_ch =new Node(4); left_ch->children.push_back(নতুন নোড(5)); left_ch->children.push_back(নতুন নোড(6)); root->children.push_back(left_ch); root->children.push_back(mid_ch); root->children.push_back(right_ch); সমাধান ob; print_vector(ob.levelOrder(root));}

ইনপুট

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

আউটপুট