C++의 N-ary 트리 수준 순서 순회

n-ary 트리가 있다고 가정하고 노드 값의 레벨 순서 순회를 반환해야 합니다. Nary-Tree 입력 직렬화는 레벨 순서 순회로 표현됩니다. 여기에서 각 하위 그룹은 null 값으로 구분됩니다(예제 참조). 따라서 다음 트리는 [1,null,3,2,4,null,5,6]

출력은 [[1],[3,2,4],[5,6]]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 행렬을 만들고

• 루트가 null이면

  를 반환합니다.

• 하나의 큐 q를 만들고 루트 삽입

• q가 비어 있지 않은 동안

  • size :=큐의 크기

  • 하나의 어레이 온도를 만듭니다.

  • 크기가 0이 아닌 동안

    • curr :=q의 첫 번째 요소

    • temp에 curr 값 삽입

    • 대기열에서 요소 삭제

    • 범위 0에서 curr의 자식 크기까지의 i에 대해

      • curr의 i번째 자식 삽입

    • 크기를 1로 줄입니다.

  • ans에 temp 삽입

• 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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, ],]