剑指 Offer 32

/**
 * 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) {
        // 队列用于层序遍历
        Queue<TreeNode> queue = new LinkedList<>();
        // 二维数组用于存放每一层的所有节点
        List<List<Integer>> res = new ArrayList<>();
        // 根节点入队
        if(root != null) queue.add(root);
        while(!queue.isEmpty()) {
            // 存放每一层的结点
            List<Integer> tmp = new ArrayList<>();
            // queue.size()为当前层的结点数
            for(int i = queue.size(); i > 0; i --) {
                TreeNode node = queue.poll(); // 删除并返回队头的元素
                tmp.add(node.val);
                // 左孩子不空则放入队列
                if(node.left != null)   queue.add(node.left);
                // 右孩子不空则放入队列
                if(node.right != null)  queue.add(node.right);
            }
            res.add(tmp);   // 将该层的所有节点加入res中
        }
        return res;
    }
}