层序遍历

简单易懂的写法：用一个List模拟队列，设置一个每层最后一个节点指针last，每当队头front和last相等，则说明当前已经遍历到该层的最后一个节点，需要把该层的所有元素加到返回结果中。同时，last指针的值也更新为rear即可（当前已经遍历到该层的最后一个节点了，那么这个节点的右子节点必定为下一层的最后一个节点，如果右子节点为空，那么下一层的最后一个节点就是左子节点）。

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        int front = 0;
        int rear = 0;
        int last = 1;
        List<TreeNode> list = new ArrayList<TreeNode>();
        list.add(root);
        rear++;
        ArrayList<ArrayList<Integer>> res= new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> temp = new ArrayList<Integer>();
        if(root==null)return res;
        while(front!=rear){
            TreeNode p = list.get(front);
            ++front;
            temp.add(p.val);
              if(p.left!=null){
                list.add(p.left);
                rear++;
            }
            if(p.right!=null){
                list.add(p.right);
                rear++;
            }
             if(last==front){
                last = rear;
                res.add(new ArrayList<Integer>(temp));
                temp.clear();
            }
        }
        return res;
    }
}