算法思想

题目含义：对于每一层，都从左到右打印，也就是层序遍历，层序遍历的实现方式是 bfs，那么直接用bfs就可以了

class Solution {
    public List<Integer> printFromTopToBottom(TreeNode root) {
        if(root == null) return new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();

        q.offer(root);

        while(q.size() != 0)
        {
            TreeNode node = q.poll();
            list.add(node.val);
            if(node.left != null) q.offer(node.left);
            if(node.right != null) q.offer(node.right);
        }
        return list;
    }
}

但是题目有意思的一点是，要把每一层都放到一个 list中去; 看到题目的样例,可以发现除了root外，每层后面都有 null，所以我们可以联想到 判断每个节点的后面为不为空，为空的话就把list加入到res中，然后把list清空就可以了：

输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
    8
   / \
  12  2
     /
    6
   /
  4

输出：[[8], [12, 2], [6], [4]]
(8, null, 12, 2, null, 6, null, 4, null)

if(node.left != null) q.offer(node.left);
if(node.right != null) q.offer(node.right);

但是这段代码保证了不会有 null 加入到 队列 中去，所以我们要手动加入，在每层后面加入null，然后分情况讨论；

每取出一个节点，都会把它的左右节点都加入到队列中去，所以我们加入的null 就会加入到 每层的后面

卡点：我被卡在了在什么时候加null了，在每行后面加个null，当q为空时就不用加了，所以可以设置为

if(q.size() != 0) q.offer(null);

java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> printFromTopToBottom(TreeNode root) {
        if(root == null) return new ArrayList<>();

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();

        q.offer(root);
        q.offer(null);

        while(q.size() != 0)
        {
            TreeNode node = q.poll();
            if(node != null)
            {
                list.add(node.val);
                if(node.left != null) q.offer(node.left);
                if(node.right != null) q.offer(node.right);    // 在这里会把下一层的节点也会加进去
            }
            else
            {
                if(q.size() != 0) q.offer(null);              // [8, null, 12, 2]
                List<Integer> tmp = new ArrayList<>(list);
                res.add(tmp);
                list.clear();
            }
        }
        return res;
    }
}