440，剑指 Offer-从上到下打印二叉树 II
You should never judge something you don't understand.
你不应该去评判你不了解的事物。
问题描述
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
提示：
节点总数 <= 1000
BFS解决
这题和上一题439，剑指 Offer-从上到下打印二叉树其实是一样的，只不过上一题返回的是数组，这一题返回的是list。返回数组，我们还要初始化数组，但不知道数组的大小，所以一般是先储存在list中再转化为数组，返回list就比较简单了。
1public List<List<Integer>> levelOrder(TreeNode root) {
2 //边界条件判断
3 if (root == null)
4 return new ArrayList<>();
5 //队列
6 Queue<TreeNode> queue = new LinkedList<>();
7 List<List<Integer>> res = new ArrayList<>();
8 //根节点入队
9 queue.add(root);
10 //如果队列不为空就继续循环
11 while (!queue.isEmpty()) {
12 //BFS打印，levelNum表示的是每层的结点数
13 int levelNum = queue.size();
14 //subList存储的是每层的结点值
15 List<Integer> subList = new ArrayList<>();
16 for (int i = 0; i < levelNum; i++) {
17 //出队
18 TreeNode node = queue.poll();
19 subList.add(node.val);
20 //左右子节点如果不为空就加入到队列中
21 if (node.left != null)
22 queue.add(node.left);
23 if (node.right != null)
24 queue.add(node.right);
25 }
26 //把每层的结点值存储在res中，
27 res.add(subList);
28 }
29 return res;
30}
DFS解决
这题让一层一层的打印，其实就是BFS，但使用DFS也是可以解决的，看一下
1public List<List<Integer>> levelOrder(TreeNode root) {
2 List<List<Integer>> res = new ArrayList<>();
3 levelHelper(res, root, 0);
4 return res;
5}
6
7public void levelHelper(List<List<Integer>> list, TreeNode root, int level) {
8 //边界条件判断
9 if (root == null)
10 return;
11 //level表示的是层数，如果level >= list.size()，说明到下一层了，所以
12 //要先把下一层的list初始化，防止下面add的时候出现空指针异常
13 if (level >= list.size()) {
14 list.add(new ArrayList<>());
15 }
16 //level表示的是第几层，这里访问到第几层，我们就把数据加入到第几层
17 list.get(level).add(root.val);
18 //当前节点访问完之后，再使用递归的方式分别访问当前节点的左右子节点
19 levelHelper(list, root.left, level + 1);
20 levelHelper(list, root.right, level + 1);
21}
总结
这题其实就是二叉树的宽度优先搜索，前面讲373，数据结构-6,树的时候也提到过树的各种遍历方式。
长按上图，识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧
本文分享自微信公众号 - 数据结构和算法（sjjghsf）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
