C++でのN-aryツリーレベルの順序トラバーサル

n-aryツリーがあるとすると、そのノードの値のレベル順トラバーサルを返す必要があります。 Nary-Tree入力のシリアル化は、レベル順の走査で表されます。ここでは、子の各グループがnull値で区切られています（例を参照）。したがって、次のツリーは[1、null、3,2,4、null、5,6]

出力は[[1]、[3,2,4]、[5,6]]

これを解決するには、次の手順に従います-

• 1つの行列を作成します

• ルートがnullの場合、ansを返します

• 1つのキューをqにして、ルートを挿入します

• qが空ではない間

  • size：=キューのサイズ

  • 1つのアレイを一時的に作成

  • サイズが0ではない場合

    • curr：=qの最初の要素

    • currの値をtempに挿入します

    • キューから要素を削除する

    • 0からcurrの子のサイズまでの範囲のiの場合

      • currのi番目の子を挿入します

    • サイズを1つ減らします

  • 温度を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, ],]