/**
 * @author wuze
 * @desc ...
 * @date 2021-03-15 10:49:56
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;





//给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
/*
思路：
层序遍历，bfs，借助队列，对每一层，结点一进一出
 */
public class 二叉树的层序遍历_102 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //借助队列，每进一个，就出一个，记录每一层的level和节点数
    //List的List。每个List的节点，存储一个List（内层List存储每一层中的节点数（即level中的nodel））(外层存储每一个level)
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        if(root==null){
            return res;//输出空值，不能输出null值（不符合题目输出规范）
        }
        //队列中每个结点存储的是 树的节点TreeNode，队列可以用一个LinkedList表示
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        /*
        offer ()　　将指定的元素插入此队列（如果立即可行且不会违反容量限制），插入成功返回 true；
        否则返回 false。当使用有容量限制的队列时，offer 方法通常要优于 add 方法 ——add 方法可能无法插入元素，
        而只是抛出一个  IllegalStateException 异常

        add ()　　将指定的元素插入此队列
         */
        queue.offer(root);//将头结点入队列
        while(!queue.isEmpty()){//当队列不为空
            List<Integer> level=new ArrayList<>();
            int curSize = queue.size();//每次的size是不一样的
            for(int i=0;i<curSize;i++){
                /*区别
                poll () 　　获取并移除此队列的头，如果此队列为空，则返回 null
                remove ()　　获取并移除此队列的头，如果此队列为空，则抛出 NoSuchElementException 异常

                peek ()　　获取队列的头但不移除此队列的头。如果此队列为空，则返回 null
                 */
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left!=null){
                    queue.offer(node.left);
                }
                if(node.right!=null){
                    queue.offer(node.right);
                }
            }
            //遍历完一层
            res.add(level);
        }
        return res;
    }

}