这是悦乐书的第225次更新，第238篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第92题（顺位题号是429）。给定n-ary树，返回其节点值的级别顺序遍历。（即，从左到右，逐级）。例如，给定一个3-ary树：
我们应该返回它的级别顺序遍历：
[[1]，[3,2,4][5,6]]
注意：
-
树的深度最多为1000。
-
节点总数最多为5000。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
使用广度优先算法（BFS），一级一级，从左往右遍历，对此我们借助队列来实现。
特殊情况：当root为null时，直接返回一个没有任何元素的list。
正常情况：先将root放入队列，然后开始循环，最外层循环，我们新建一个list，存入每一级的元素，第二层循环开始处理队列中上一轮被添加进去的node，依次poll出来，将其val存入外层循环新建的list中，而其另一个属性children，因为是一个以node为元素的数组，所以在此使用for-each循环，将其添加进队列中，在下一轮循环时再从队列中取出。
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
}
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> current = new ArrayList<>();
int length = queue.size();
for (int i=0; i<length; i++) {
Node curr = queue.poll();
current.add(curr.val);
for (Node n : curr.children) {
queue.offer(n);
}
}
result.add(current);
}
return result;
}
}
03 第二种解法
使用深度优先算法（DFS），此方法就需要使用递归来操作了。
在树的每一级，都可以看做是当前问题的子问题，因此我们将数组、根节点、层级这三个要素作为递归的条件。在递归方法中，如果当前节点为null，直接return；如果当前result的大小和层级相等，就往result新加一个list，然后从result中取出当前层级对应的数组，先将当前节点值添加进去，然后for-each遍历其children，每一个children都符合当前问题的描述，在此调用方法自身，但是第三个参数层级需要往上加1，因为进入了当前节点的下一层级。
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
}
class Solution {
public List<List<Integer>> levelOrder(Node root) {
List<List<Integer>> result = new ArrayList<>();
levelOrder(root, result, 0);
return result;
}
public void levelOrder(Node root, List<List<Integer>> result, int level) {
if (root == null) {
return ;
}
if (result.size() == level) {
result.add(new ArrayList<>());
}
List<Integer> list = result.get(level);
list.add(root.val);
for (Node n : root.children) {
levelOrder(n, result, level+1);
}
}
}
04 小结
算法专题目前已连续日更超过两个月，算法题文章92+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！