【hot100】102二叉树的层序遍历

一、思路

经典队列应用，将根节点入队，然后每出队一个节点再把其子节点加入队列

二、记忆

1.Queue和Deque的联系和区别

Queue<TreeNode> queue = new LinkedList<TreeNode>(); 和 Deque<TreeNode> list = new LinkedList<TreeNode>(); 虽然都基于 LinkedList 实现，但它们的接口类型不同，导致可用的操作和行为不同。以下是具体区别：
 

1. 接口定义与设计目的

类型	接口功能	设计场景
Queue	表示标准的先进先出（FIFO）队列，仅支持尾部添加、头部移除的操作。	需要严格遵循队列行为（如任务调度、广度优先搜索）。
Deque	表示双端队列（Double-Ended Queue），支持两端添加或移除元素，可模拟栈或队列。	需要灵活操作两端（如滑动窗口、栈/队列混合操作）。

2. 方法对比

以下方法在两种接口中的可用性不同：

操作	Queue 支持	Deque 支持	说明
添加元素到尾部	offer(e)	offerLast(e)	队列的默认添加行为。
从头部移除元素	poll()	pollFirst()	队列的默认移除行为。
查看头部元素（不移除）	peek()	peekFirst()	查看队列头部。
添加元素到头部	❌	offerFirst(e)	Deque 特有，允许头部插入（类似栈的 push）。
从尾部移除元素	❌	pollLast()	Deque 特有，允许从尾部移除元素。
栈操作（后进先出）	❌	push(e)/pop()	Deque 可以模拟栈的行为（push=头部插入，pop=头部移除）。

三、代码

public List<List<Integer>> levelOrder(TreeNode root){
        if (root == null) return new ArrayList<>();
        List<List<Integer>> ret = new ArrayList<>();
        Deque<TreeNode> list = new LinkedList<TreeNode>();
        list.addLast(root);

        while(!list.isEmpty()){//每层
            List<Integer> templist = new ArrayList<>();
            int length = list.size();
            for (int i = 0;i<length;i++){//每颗子树
                TreeNode temp = list.pollFirst();
                templist.add(temp.val);
                if (temp.left!=null){
                    list.addLast(temp.left);
                }
                if (temp.right!=null){
                    list.addLast(temp.right);
                }
            }
            ret.add(templist);

        }
        return ret;
    }