题意

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

例如：
给定二叉树 [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;
    }
}