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; } }
- 还没有人评论，欢迎说说您的想法！
客服
