分析
利用层序遍历可以将每层的节点加入到队列中,问题是要控制每层的个数,可以用size变量来记录每一层有多少个节点,每当每一层最右边的点入队后,此时队的数量就是下一层节点的数量。每出队一个,size--,减为0时说明这一层结束,又将队列的数量赋给size。
/*
// Definition for a Node.
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:
queue<Node*> q;
vector<vector<int>> ans;
vector<int> cur;
vector<vector<int>> levelOrder(Node* root) {
if(!root)return ans;
q.push(root);
int size=1;
while(q.size()){
auto t = q.front();
q.pop();
cur.push_back(t->val);
for(auto cc:t->children){
q.push(cc);
}
--size;
if(size==0){
size=q.size();
ans.push_back(cur);
cur.clear();
}
}
return ans;
}
};