题目：

429. N 叉树的层序遍历

题解：广度优先搜索BFS

方法一：广度优先搜索BFS
思路与算法：

对于「层序遍历」的题目，我们一般使用广度优先搜索。在广度优先搜索的每一轮中，我们会遍历同一层的所有节点。

具体地，我们首先把根节点 root 放入队列中，随后在广度优先搜索的每一轮中，我们首先记录下当前队列中包含的节点个数（记为 cnt），即表示上一层的节点个数。在这之后，我们从队列中依次取出节点，直到取出了上一层的全部 cnt 个节点为止。当取出节点 cur 时，我们将cur 的值放入一个临时列表，再将 cur 的所有子节点全部放入队列中。

当这一轮遍历完成后，临时列表中就存放了当前层所有节点的值。这样一来，当整个广度优先搜索完成后，我们就可以得到层序遍历的结果。

细节：

需要特殊判断树为空的情况。

代码：广度优先搜索BFS

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class lc_429 {

    public static List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null)
        {
            return res;
        }
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        while(!queue.isEmpty())
        {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for(int i = 0; i < size; i++)
            {
                Node node = queue.poll();
                level.add(node.val);
                for(int j = 0; j < node.children.size(); j++)
                {
                    if(node.children.get(j) != null)
                    {
                        queue.offer(node.children.get(j));
                    }
                }
            }
            res.add(level);
        }
        return res;
    }

    public static void main(String[] args) {

    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

参考：

1. N 叉树的层序遍历
2. 【宫水三叶】树的（层序）遍历运用题
3. 广度优先搜索原理与实践
4. DFS（深度优先搜索）和BFS(广度优先搜索)
5. 广度优先遍历与最短路径
6. 【算法入门】广度/宽度优先搜索(BFS)