题目

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

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