说明
连续在LeetCode中看到好几个类似的题目，核心思想就是树的广度优先搜索(BFS)，并在搜索的过程中记录每一层的值。
以LeetCode中的N-ary Tree Level Order Traversal为例：
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:
example-img
We should return its level order traversal:
[
[1],
[3,2,4],
[5,6]
]
解析
利用队列使用BFS。设res为要返回的2维数组, vec为当前访问层的元素的1维数组。
- count为当前层的节点数量，初始化为0，newCount为新加入的一层的节点数量，初始化为0，c为当前访问层的第几个元素，初始化为0.
- 根节点入队，++count, 根节点元素加入到vec中
- 如果c等于count,将1维数组vec加入到res中，并使 count = newCount, c = 0, newCount = 0, 再清空vec
- 队列中的第一个元素出队，并赋值给p，对于p中的每一个子节点，如果不为空则进队并使newCount = newCount+1
- 节点p的元素加入到vec中， 并让 c = c + 1
- 重复步骤3-5直到队列为空
- 如果count大于0，则将vec中加入到res中
时间复杂度： O(n) n为节点的数量
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;
}();
这个题中不得不提一下c++中cin的优化问题，优化代码如上，主要就是关闭stdio同步和解除与cout的绑定，这份代码在LeetCode提交没优化cin之前大概为比20%的提交快，而开了cin优化便几乎比100%的提交快了...
关于cin读取数据的问题见这篇文章
本作品采用知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议进行许可。转载请注明: 作者staneyffer，首发于我的博客，原文链接: https://chengfy.com/post/8
