Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

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

     3
    / \
   9  20
     /  \
    15   7

return its level order traversal as:

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

Java

public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> rst = new ArrayList<List<Integer>>();
        List<Integer> items = new ArrayList<Integer>();
        LinkedList<TreeNode> cur = new LinkedList<TreeNode>();
        LinkedList<TreeNode> nxt = new LinkedList<TreeNode>();

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

        while(!cur.isEmpty()) {
            TreeNode now = cur.poll();
            items.add(now.val);

            if(now.left != null) {
                nxt.add(now.left);
            } 
            if(now.right != null) {
                nxt.add(now.right);
            }

            if(cur.isEmpty()) {
                cur.addAll(nxt);
                // Why should we create new ArrayList here?
                rst.add(new ArrayList<Integer>(items));
                items.clear();
                nxt.clear();
            }
        }
        return rst;
    }
}