### Description

Given an n-ary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

For example, given a 3-ary tree:

We should return its level order traversal:

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

``````

### 解析

1. count为当前层的节点数量，初始化为0，newCount为新加入的一层的节点数量，初始化为0，c为当前访问层的第几个元素，初始化为0.
2. 根节点入队，++count, 根节点元素加入到vec中
3. 如果c等于count,将1维数组vec加入到res中，并使 count = newCount, c = 0, newCount = 0, 再清空vec
4. 队列中的第一个元素出队，并赋值给p，对于p中的每一个子节点，如果不为空则进队并使newCount = newCount+1
5. 节点p的元素加入到vec中， 并让 c = c + 1
6. 重复步骤3-5直到队列为空
7. 如果count大于0，则将vec中加入到res中

### C++实现

``````/*
// Definition for a Node.
class Node {
public:
int val = NULL;
vector<Node*> children;

Node() {}

Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public:
vector<vector<int>> levelOrder(Node* root) {
vector<vector<int>> res;
if(root == NULL)
return res;
int count = 0;
int newCount = 0;
int c = 0;
vector<int> vec;    // all node`val at same level

queue<Node*> q;
q.push(root);
count = 1;

while(!q.empty()){
if(c == count){
res.push_back(vec);
vec.clear();
count = newCount;
c = 0;
newCount = 0;
}
auto p = q.front();
q.pop();
vec.push_back(p->val);
for(int i = 0; i < p->children.size(); ++i){
if(p->children[i] != NULL){
q.push(p->children[i]);
++newCount;
}
}
++c;
}
if(count){ // last leavel values
res.push_back(vec);
}
return res;
}
};
// cin优化
static const auto __ = [](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
return nullptr;
}();

``````