原题
给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。
例如，给定一个 3叉树 :
返回其层序遍历:
[
[1],
[3,2,4],
[5,6]
]
说明:
1. 树的深度不会超过 1000。
2. 树的节点总数不会超过 5000。
解法
思想
类似leetcode102-二叉树的层次遍历，通过DFS或BFS实现。
代码
迭代（BFS）：
class Solution {
public List<List<Integer>> levelOrder(Node root) {
Queue<Node> queue = new LinkedList<>();
List<List<Integer>> ans = new ArrayList<>();
List<Integer> cur = new ArrayList<>();
if(root == null) return new ArrayList<List<Integer>>();
queue.offer(root);
queue.offer(null);//以null作为每层结束的标志符
while(!queue.isEmpty()){
Node node = queue.poll();
if(node == null){
if(cur.size()!=0) ans.add(cur);
cur = new ArrayList<>();
}else{
cur.add(node.val);
for(Node child:node.children){
if(child!=null) queue.offer(child);
}
//若队首为null说明这一层的节点的子节点已经全部加入队列了，需要加入一个null
if(queue.peek()==null) queue.offer(null);
}
}
return ans;
}
}
递归（DFS）：
class Solution {
List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> levelOrder(Node root) {
if(root==null)
return ans;
DFS(root,0);
return ans;
}
public void DFS(Node root,int level){
if(ans.size()==level)
ans.add(new ArrayList<Integer>());
ans.get(level).add(root.val);
for(Node node:root.children){
if(node!=null)
DFS(node,level+1);
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode429-n%e5%8f%89%e6%a0%91%e7%9a%84%e5%b1%82%e5%ba%8f%e9%81%8d%e5%8e%86/
