其他
439，剑指 Offer-从上到下打印二叉树
Happiness can be found, even in the darkest of times.
可我们总能找到快乐，哪怕处在最黑暗的时期。
问题描述
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回：
[3,9,20,15,7]
提示：
节点总数 <= 1000
BFS解决
其实这就是二叉树的BFS，也可以看下之前讲的373，数据结构-6,树，
就是这样，一层一层打印，使用队列解决
1public int[] levelOrder(TreeNode root) {
2 if (root == null)
3 return new int[0];
4 //队列
5 Queue<TreeNode> queue = new LinkedList<>();
6 List<Integer> list = new ArrayList<>();
7 //根节点入队
8 queue.add(root);
9 while (!queue.isEmpty()) {
10 //出队
11 TreeNode node = queue.poll();
12 //把结点值存放到list中
13 list.add(node.val);
14 //左右子节点如果不为空就加入到队列中
15 if (node.left != null)
16 queue.add(node.left);
17 if (node.right != null)
18 queue.add(node.right);
19 }
20 //把list转化为数组
21 int[] res = new int[list.size()];
22 for (int i = 0; i < list.size(); i++) {
23 res[i] = list.get(i);
24 }
25 return res;
26}
递归方式解决
其实这题很明显就是二叉树的宽度优先搜索，使用上面代码就对了。实际上我们还可以改一下，改成DFS并且还是递归的，我想除了我应该没人会这么无聊吧，有兴趣的也可以看下
1public int[] levelOrder(TreeNode root) {
2 List<List<Integer>> list = new ArrayList<>();
3 levelHelper(list, root, 0);
4 List<Integer> tempList = new ArrayList<>();
5 for (int i = 0; i < list.size(); i++) {
6 tempList.addAll(list.get(i));
7 }
8
9 //把list转化为数组
10 int[] res = new int[tempList.size()];
11 for (int i = 0; i < tempList.size(); i++) {
12 res[i] = tempList.get(i);
13 }
14 return res;
15}
16
17public void levelHelper(List<List<Integer>> list, TreeNode root, int height) {
18 if (root == null)
19 return;
20 if (height >= list.size()) {
21 list.add(new ArrayList<>());
22 }
23 list.get(height).add(root.val);
24 levelHelper(list, root.left, height + 1);
25 levelHelper(list, root.right, height + 1);
26}
总结
这题实际上就是二叉树的宽度优先遍历，一层一层打印。
长按上图，识别图中二维码之后即可关注。
如果觉得有用就点个"赞"吧