Leetcode之广度优先搜索（BFS）专题-详解429. N叉树的层序遍历（N-ary Tree Level Order Traversal）

qinyuguan 2019-08-31 原文

Leetcode之广度优先搜索（BFS）专题-429. N叉树的层序遍历（N-ary Tree Level Order Traversal）

给定一个 N 叉树，返回其节点值的层序遍历。 (即从左到右，逐层遍历)。

例如，给定一个 3叉树 :

返回其层序遍历:

[
     [1],
     [3,2,4],
     [5,6]
]

说明:

树的深度不会超过 1000。
树的节点总数不会超过 5000。

分析：

广度优先搜索，又可以叫层次遍历，就像这题，我们一层一层地遍历这个树。

广度优先搜索需要一个Queue，Queue的创建在Java中可以使用Queue<Object> queue = new LinkedList<>();

关于Queue的函数的区别，请点击学习笔记之Java队列Queue中offer/add函数,poll/remove函数,peek/element函数的区别进行了解。

这题，我们首先new一个Queue，然后把根节点加入。

然后，一个条件while(!Queue.isEmpty())，即如果队列不为空，则一直循环，若队列为空，证明已经搜索完毕。

进入这个循环后，我们把队列里的所有元素一个一个取出来，再把它们的children节点加进去。

在这个途中，我们记录下每个节点的值，最后返回答案。

举例：

题中这个三叉树，我们首先把1加入队列。

队列的状态如下： 1

然后取1出来，把1的子节点都加入

队列的状态如下： 3 2 4

取3出来，把3的子节点加入

队列的状态如下： 2 4 5 6

取2，把2的子节点加入，2没有子节点

队列的状态如下： 4 5 6

取4，把4的子节点加入，4没有子节点

队列的状态如下： 5 6

取5，5没有子节点

队列的状态如下： 6

取6，6没有子节点

队列的状态如下：空

发现队列为空，结束，初学者可以自己按照题目的例子，在纸上写一遍BFS的流程，方便理解。

总的来说，BFS就是把下一层可以达到的点/节点，全部加入到队列中，所以称之为层次遍历。

这题的AC代码：

/*
// 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>> ans = new ArrayList<>();
        if (root == null) return ans;
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i=0;i<size;i++){
                Node node = queue.poll();
                list.add(node.val);
                for(Node n:node.children){
                    queue.offer(n);
                }
            }
            ans.add(list);
            
        }
        return ans;
    }
}