题目
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
题解
使用队列先进先出的特性，按层将节点入队，并出队。再将出队按层对应顺序添加到LinkedList中。
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) {
return res;
}
Queue<TreeNode> dq = new LinkedList<>();
dq.offer(root);
boolean right = true;
while (!dq.isEmpty()) {
LinkedList<Integer> inRes = new LinkedList<>();
int levelCount = dq.size();
while (levelCount-- > 0) {
TreeNode td = dq.poll();
if (td.left != null) {
dq.offer(td.left);
}
if (td.right != null) {
dq.offer(td.right);
}
if (right) {
inRes.offerLast(td.val);
} else {
inRes.offerFirst(td.val);
}
}
right = !right;
res.add(inRes);
}
return res;
}
}
