Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree {3,9,20,#,#,15,7},

     3
    / \
   9  20
     /  \
    15   7

return its zigzag level order traversal as:

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

Java

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> sols = new ArrayList<List<Integer>>();
        List<Integer> sol = new ArrayList<Integer>();
        LinkedList<TreeNode> cur = new LinkedList<TreeNode>();
        LinkedList<TreeNode> next = new LinkedList<TreeNode>();
        int count = 0;

        if(root == null) {
            return sols;
        }
        cur.add(root);

        while(!cur.isEmpty()) {
            TreeNode node = cur.poll();
            if(node.left != null) {
                next.add(node.left);
            }
            if(node.right != null) {
                next.add(node.right);
            }
            sol.add(node.val);
            if(cur.isEmpty()) {
                cur.addAll(next);
                next.clear();
                if(count++ % 2 != 0) {
                    Collections.reverse(sol);
                }
                sols.add(new ArrayList<Integer>(sol));
                sol.clear();
            }
        }
        return sols;
    }
}