请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

示例

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

3

/ \

9 20

/ \

15 7

返回其层次遍历结果：

[

[3],

[20,9],

[15,7]

]

提示

节点总数 <= 1000

方法：双端队列+BFS

算法流程：

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

• 初始化：初始结果集合、初始队列并加入根节点

• 循环遍历，为空时（即无叶子结点）跳出：

• 创建一个链表，用于存储每一层的叶子节点；

• 遍历每一层叶子节点，从队列弹出元素；

• 根据结果集合的大小来判断当前树的层数，如果是偶数，加在链表尾部；否则加到链表头部；

• 判断左/右子节点非空，加入到队列中，进行下一次遍历；

• 返回结果集合；

图解说明：

方法如下：

细节处理

• 细节1：基于 双端队列的特点，偶数行"按照从左到右的顺序打印"，奇数行"按照从右到左的顺序打印"

• 细节2：i = queue.size()，避免size的大小改变

• 细节3：根据结果集合的大小来判断当前树的层数

复杂度分析

• 时间复杂度：O(n)，每个节点入队出队各一次。

• 空间复杂度：O(n)，二叉树的节点的个数。

END

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

宝剑锋从磨砺出，梅花香自苦寒来，赠友人。