剑指 Offer — 从上到下打印二叉树

复仇Bytedance之路

题目描述：

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例如: 给定二叉树: [3,9,20,null,null,15,7],

3 / \ 9 20 / \ 15 7

返回：

[3,9,20,15,7]

提示：

节点总数 <= 1000

题解

典型的程序遍历即广度优先搜索（BFS）。BFS 是借助队列的先入先出特性实现的：

算法流程：

特例处理： 当树的根节点为空，则直接返回空列表 [] ；初始化： 打印结果列表 res = [] ，包含根节点的队列 queue = [root] ；BFS 循环： 当队列 queue 为空时跳出； 出队： 队首元素出队，记为 node；打印： 将 node.val 添加至列表 tmp 尾部；添加子节点： 若 node 的左（右）子节点不为空，则将左（右）子节点加入队列 queue ；返回值： 返回打印结果列表 res 即可。 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int[] levelOrder(TreeNode root) { if(root == null) return new int[0]; Queue<TreeNode> queue = new LinkedList<>(); ArrayList<Integer> ans = new ArrayList<>(); queue.offer(root); while(!queue.isEmpty()) { TreeNode node = queue.poll();//队列非空的时候不断弹出 ans.add(node.val);//写到结果中 if(node.left != null) queue.offer(node.left);//处理完了当前节点就去处理其叶子 if(node.right != null) queue.offer(node.right); } int[] res = new int[ans.size()]; for(int i = 0; i < ans.size(); i++) res[i] = ans.get(i); return res; } }

代码有几处值得关注的地方

java中Queue的底层是使用链表来实现的，因此初始化一个Queue的时候是Queue<TreeNode> queue = new LinkedList<>();队列的入队出队有两对操作方法（推荐第一种）： offer/poll：入队失败会返回false，出队成功就返回队首值，失败就返回nulladd/remove：操作失败会报异常

List转数组报错

在最后想节省空间使用ans.toArray(new int[0])进行返回时报错：

error: no suitable method found for toArray(int[]) primeList.toArray(primeArray); method ArrayList.toArray(Object[]) is not applicable (actual argument int[] cannot be converted to Object[] by method invocatio n conversion)

啥意思呢？编译器给出的错误说我们调用的方法（List.toArray(T[])）不适用于int[]类型的参数，只是因为int不是Object（它是原始类型）。 好的，意思就是我把int换成Integer就完事儿了呗。对不起还是在报错：

error: incompatible types: inference variable T has incompatible bounds

但还是说类型错了，为啥？因为在Java8中Arrays.asList不会自动拆箱装箱操作！，因此这种列表转数组的方式对int[]并不起作用，还是需要笨比的去遍历！！！

String[] 是可以的！