给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如： 给定二叉树 [3,9,20,null,null,15,7],
代码语言：javascript复制 3
/
9 20
/
15 7返回锯齿形层次遍历如下：
代码语言：javascript复制[
[3],
[20,9],
[15,7]
]BFS（广度优先遍历） 思路
最直观的方法是 BFS，逐层遍历树。
BFS 在每层的默认顺序是从左到右，因此需要调整 BFS 算法以生成锯齿序列。
最关键的是使用双端队列遍历，可以在队列的任一端插入元素。
如果需要 FIFO （先进先出）的顺序，则将新元素添加到队列尾部，后插入的元素就可以排在后面。如果需要 FILO （先进后出）的顺序，则将新元素添加到队列首部，后插入的元素就可以排在前面。
算法
实现 BFS 的几种算法。
使用两层嵌套循环。外层循环迭代树的层级，内层循环迭代每层上的节点。
也可以使用一层循环实现 BFS。将要访问的节点添加到队列中，使用 分隔符（例如：空节点）把不同层的节点分隔开。分隔符表示一层结束和新一层开始。
这里采用第二种方法。在此算法的基础上，借助双端队列实现锯齿形顺序。在每一层，使用一个空的双端队列保存该层所有的节点。根据每一层的访问顺序，即从左到右或从右到左，决定从双端队列的哪一端插入节点。
实现从左到右的遍历顺序（FIFO）。将元素添加到队列尾部，保证后添加的节点后被访问。从上图中可以看出，输入序列 [1, 2, 3, 4, 5]，按照 FIFO 顺序得到输出序列为 [1, 2, 3, 4, 5]。
实现从右到左的遍历顺序（FILO）。将元素添加到队列头部，保证后添加的节点先被访问。输入序列 [1, 2, 3, 4, 5]，按照 FILO 顺序得到输出序列为 [5, 4, 3, 2, 1]。
代码语言：javascript复制class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<List<Integer>>();
}
boolean isleftToRight = true;
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> level_list = new LinkedList<Integer>();
LinkedList<TreeNode> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
nodeQueue.add(null);
while (!nodeQueue.isEmpty()) {
TreeNode treeNode = nodeQueue.poll();
if (treeNode != null) {
if (treeNode.left != null) nodeQueue.add(treeNode.left);
if (treeNode.right != null) nodeQueue.add(treeNode.right);
if (isleftToRight) {
level_list.addLast(treeNode.val);
} else {
level_list.addFirst(treeNode.val);
}
} else {
result.add(level_list);
level_list = new LinkedList<Integer>();
if (nodeQueue.size() > 0)
nodeQueue.addLast(null);
isleftToRight = !isleftToRight;
}
}
return result;
}
}
