题意
给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回锯齿形层序遍历如下：
[
[3],
[20,9],
[15,7]
]
题解
利用队列进行求解。1）每一行记录队列的size，然后出队列，并把当前节点的左右节点塞入队列 2）利用linkedList队列按照方向保存节点数据。
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ress = new ArrayList<>();
if (root == null) {
return ress;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
// 记录当前获取到的节点
TreeNode curNode = root;
// 记录方向
boolean right = true;
while (!queue.isEmpty()) {
// 记录当前行数据size
int size = queue.size();
LinkedList<Integer> res = new LinkedList<>();
// 每行数据出队列，直到队列全部出完
while (size-- > 0) {
curNode = queue.poll();
// 将出队列的节点左右子节点入队列
if (curNode.left != null) {
queue.offer(curNode.left);
}
if (curNode.right != null) {
queue.offer(curNode.right);
}
// 根据方向，将取出来的值塞入每行的list
if (right) {
res.offerLast(curNode.val);
} else {
res.offerFirst(curNode.val);
}
}
right = !right;
ress.add(res);
}
return ress;
}
}
