直接在队列中添加分层信息

在队列中使用null节点标志一行的结束。
每次从队列中取出一个元素：

• 若是null：说明此行出队已经结束，同时下一行节点的入队也已经结束，那么就再在队列尾部添加null标志。
• 若不是null:继续遍历当前行的元素。

例子：
     1
   /   \
  2     3
 / \   / \
4   5  6  7

队列初始状态:                            [null][1]=>
1出队,2,3入队：                          [3][2][null]=>
null出队,一行结束，向队尾添加null标志：    [null][3][2]=>
2出队，4，5入队：                        [5][4][null][3]=>
3出队，6，7入队：                        [7][6][5][4][null]=>
null出队,一行结束，向队尾添加null标志:    [null][7][6][5][4]=>
4.5.6.7依次出队：                       [null]=>
null出队后发现链表为空，说明层次遍历结束，不再向队尾添加null
......

代码如下：

import java.util.*;

public class Solution {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> lists=new ArrayList<>();
        if(pRoot==null) return lists;

        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(pRoot);
        queue.offer(null);//分行符号

        ArrayList<Integer> list=new ArrayList<>();//存储一行的结果
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();

            if(node==null){
                if(!queue.isEmpty()) queue.offer(null);//添加换行标志，一定要先判断队列不为空
                lists.add(list);//把此行结果加入lists
                list=new ArrayList<Integer>();//为新的一行申请空间
            }
            else{
                if(node.left!=null) queue.offer(node.left);
                if(node.right!=null) queue.offer(node.right);
                list.add(node.val);
            }
        }
        return lists;
    }
}

时间复杂度O(n)
空间复杂度O(w) w表示树的最大宽度，也就是链表的最大长度