[leetcode]_Binary Tree Level Order Traversal I && II

题目：给定一棵二叉树，对其进行层次遍历，将遍历结果存入二维链表中。

思路：二叉树的层次遍历关键在于使用Queue。

复习：

Queue的定义。LinkedList实现了Queue接口，因此可用LinkedList来初始化一个Queue。

Queue的使用。

　　1、offer()，入队，当队列满掉时，返回false。

　　2、poll()，返回队列头部元素并删除，当队列为空时，返回null。

　　3、peek()，返回队列头部元素不删除，当队列为空时，返回null。

代码：

 1     public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
 2         
 3         ArrayList<ArrayList<Integer>> level = new ArrayList<ArrayList<Integer>>();
 4      
 5         if(root == null) return level; //在面试时，可询问考官，当root== null时，返回空链表，还是null。
 6         
 7         Queue<TreeNode> q = new LinkedList<TreeNode>();
 8         q.offer(root);
 9         q.offer(new TreeNode(Integer.MAX_VALUE)); //作为层与层直接的间隔符
10         
11         ArrayList<Integer> oneLevel = new ArrayList<Integer>();
12         
13         while(!q.isEmpty()){
14             TreeNode node = q.poll();
15             
16             if(node.val != Integer.MAX_VALUE){
17                 
18                 oneLevel.add(node.val);
19                 if(node.left != null) q.offer(node.left);
20                 if(node.right != null) q.offer(node.right);
21                 
22             }else{
23                 if(oneLevel.size() == 0) break; //最后一个间隔符
24                 
25                 level.add(oneLevel);
26                 oneLevel = new ArrayList<Integer>();
27                 q.offer(new TreeNode(Integer.MAX_VALUE));
28             
29             }
30         }
31         return level;
32     }