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

示例

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

3

/ \

9 20

/ \

15 7

返回其层次遍历结果：

[

[3],

[9,20],

[15,7]

]

提示

• 节点总数 <= 1000

方法：分层遍历+BFS

• 特例处理：当树的根节点为空，则直接返回空列表

• 初始化：初始返回的结果列表，并把根节点放入到队列中

• 循环遍历：

• 根据每层的叶子节点个数遍历，注意这有个细节就是“int i = queue.size()”，因为节点出栈，节点的大小是可变的

• 节点出队

• 添加到层集合中

• 左/子节点非空时，入队，用于下层遍历

• 本层遍历结束后，把层集合放入到结果列表中

• 终止条件：返回结果列表

流程如下两个图所示。

代码如下：

复杂度分析

• 时间复杂度：O(n)，叶子结点出队和入队一次。

• 空间复杂度：O(n)，叶子结点的数量。

END

好兄弟可以点赞并关注我的公众号“javaAnswer”，全部都是干货。

业精于勤荒于嬉，行成于思毁于随，赠友人。