跬步

Queue

• Queue从字面意思就是队列，遵循着FIFO（先进先出）的原则
• Queue是一个接口。
• LinkedList实现了Deque接口，而Deque接口继承了Queue接口。
• Queue的元素添加方法有offer()和add(),推荐使用offer()方法。
• 如果容量已满时（什么情况下Queue容量会满？有的说是达到Integer.MAX_VALUE），使用add()方法会抛出IllegalStateException异常，使用offer()会返回false。
• Queue的元素删除方法有poll()和remove()，推荐使用poll()方法。
• 如果队列为空时，使用remove()方法会抛出NoSuchElementException异常,使用poll()会返回null。
• 常用方法还有peek()和element()，效果一样，都是返回头部元素。区别是如果队列为空时，peek()会返回null,而element()会抛出NoSuchElementException异常。但是如果队列有头部元素，但是元素为null,element()也会返回null。

一个例子

leetcode 107. 二叉树的层次遍历 II

给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其自底向上的层次遍历为：

[
  [15,7],
  [9,20],
  [3]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                list.add(node.val);
            }
            result.add(0, list);
        }
        return result;
    }