题目地址

思路

1. 还是层序遍历，但是相对于上一题有所变化。每层的结果单独打印成一行
2. 需要记录每层的元素个数，或者可以记录上一行元素个数
3. 根据观察，队列每次处理一层的节点前，队列中保留的是该层的所有节点，因此可以在处理队列节点前，通过队列的长度获取上一层的元素节点数目

/**
 * 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>> levelOrder(TreeNode root) {
        List<List<Integer>> matrix = new ArrayList();
        scanTree(root,matrix);
        return matrix;
    }

    // 层序遍历
    public void scanTree(TreeNode node,List matrix) {
        if (node == null) {
            return ;
        }
        // 使用队列遍历节点
        Queue<TreeNode> queue = new LinkedList();
        queue.add(node);
        // 第一层
        while(!queue.isEmpty()) {
            // 这里相当于是获取上一层节点的数目
            int levelSize = queue.size();
            ArrayList<Integer> level = new ArrayList();
            // 每次循环处理完一层的节点，这样每次队列只会剩下当层的节点
            for (int i = 0 ; i < levelSize ; i ++) {
                TreeNode tmp = queue.poll();
		// 这里添加的都是下一层的节点，但是因为有levelSize，可以知道上层节点应该处理截止的位置
                if (tmp.left != null) queue.add(tmp.left);
                if (tmp.right != null) queue.add(tmp.right);
                level.add(tmp.val);
            } 
            matrix.add(level);
        }
    }

}

Q.E.D.