題目

給定一個二叉樹，返回其節(jié)點值的鋸齒形層次遍歷。（即先從左往右，再從右往左進行下一層遍歷，以此類推，層與層之間交替進行）。

例如：
給定二叉樹 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7

返回鋸齒形層次遍歷如下：

[
[3],
[20,9],
[15,7]
]

題解

使用隊列先進先出的特性，按層將節(jié)點入隊，并出隊。再將出隊按層對應順序添加到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;
    }
}