1. 层次遍历和BFS
之前写过二叉树的前中后序遍历，不懂的点这里，今天介绍的是层次遍历，层次遍历概念很简单，我直接盗用力扣上面的图了，采用BFS也是显而易见的
2. BFS模板
还是我们最喜欢的套路模板环节，废话不多说，直接代码
1
2
3
4
5
6
7
8
9
| void bfs(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
|
BFS和关键是队列，通过先进先出的机制完成广度优先
https://leetcode-cn.com/leetbook/read/data-structure-binary-tree/xej9yc/
通过这个幻灯片就可以很好的解释了队列在二叉树层次遍历中的使用：每当一个根节点出队，就把左右子节点入队，不断循环
3. 题目：力扣102
https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
由于题目不仅要求层次遍历，还要按输出规则返回List<List<Integer>>
1
2
3
4
5
| [
[3],
[9,20],
[15,7]
]
|
因此我们需要记录每层有多少个，然后遍历这么多个并加入每层list，遍历完后才将这个list加入最终结果res，直接给ide可以测试的代码
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
| public class one_zero_two_二叉树的层次遍历 {
@Test
public void test(){
TreeNode root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);
List<List<Integer>> lists = levelOrder(root);
System.out.println(lists.toString());
}
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
List<Integer> list = new ArrayList<>();
int size = queue.size();
for(int i = 0; i < size; i++){
root = queue.poll();
list.add(root.val);
if(root.left != null) queue.offer(root.left);
if(root.right != null) queue.offer(root.right);
}
res.add(list);
}
return res;
}
}
|
其他树的题目点击这里