Binary Tree Level Order Traversal，层序遍历二叉树，每层作为list，最后返回List<list>

package LeetCode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.Queue;

class TreeNode
{
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int val)
	{
		this.val = val;
	}
}
public class BinaryTreeLevelOrderTraversal 
{
	public List<List<Integer>> levelOrder(TreeNode root)
	{
		List<List<Integer>> res = new ArrayList<>();
		if(root == null)
		{
			return res;
		}
		Deque<TreeNode> queue1 = new ArrayDeque<>();
		Deque<TreeNode> queue2 = new ArrayDeque<>();
		queue1.offer(root);
		while(!queue1.isEmpty() || !queue2.isEmpty())
		{
			List<Integer> list1 = new ArrayList<>();
			while(!queue1.isEmpty())
			{
				TreeNode temp = queue1.poll();
				if(temp.left != null)
				{
					queue2.offer(temp.left);
				}
				if(temp.right != null)
				{
					queue2.offer(temp.right);
				}
				list1.add(temp.val);
			}
			if(list1.size() != 0)//队列空的时候，list1的大小为0
			res.add(list1);
			List<Integer> list2 = new ArrayList<>();
			while(!queue2.isEmpty())
			{
				TreeNode temp = queue2.poll();
				if(temp.left != null)
				{
					queue1.offer(temp.left);
				}
				if(temp.right != null)
				{
					queue1.offer(temp.right);
				}
				list2.add(temp.val);
			}
			if(list2.size() != 0)
			res.add(list2);
		}
		
		return res;
	}
	
	public List<List<Integer>> levelOrder2(TreeNode root)
	{
		List<List<Integer>> res = new ArrayList<>();
		List<Integer> list = new ArrayList<>();
		if(root == null)
		{
			return res;
		}
		
		ArrayDeque<TreeNode> curr = new ArrayDeque<>();
		ArrayDeque<TreeNode> next = new ArrayDeque<>();
		
		curr.offer(root);
		
		while(!curr.isEmpty())
		{
			TreeNode temp = curr.poll();
			if(temp.left != null)
			{
				next.offer(temp.left);
			}
			if(temp.right != null)
			{
				next.offer(temp.right);
			}
			
			list.add(temp.val);
			
			if(curr.isEmpty())
			{
				res.add(list);
				list = new ArrayList<Integer>();
				curr = next;
				next = new ArrayDeque<>();
			}
		}
		
		return res;
	}
}