题目内容

给你二叉树的根节点 $root$，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。）

输入描述

第一行输入一个整数 $n(1 \le n \le 2000)$，表示层序遍历序列的长度。

第二行输入 $n$ 个由空格分隔的值，表示二叉树的层序遍历序列，其中 $null$ 表示空节点，非空节点值范围 $(-100 \le val \le 100)$。

输出描述

第一行输出一个整数 $k$，表示层数

接下来 $k$ 行，每行输出该层的节点值（锯齿形顺序），数字之间以空格分隔。

样例 $1$

输入

7
3 9 20 null null 15 7

输出

3
3
20 9
15 7

说明

第$1$层从左到右：$[3]$；第$2$层从右到左：$[20,9]$；第$3$层从左到右：$[15,7]$。

样例 $2$

输入

1
1

输出

1
1