【剑指offer2】 chap7 队列

七、队列 1、基础知识

Queue：
- 常用函数
  - add——offer
  - remove——poll
  - element——peek
- 接口：
  - LinkedList
  - ArrayDeque
  - PriorityQueue
Deque（双端队列）

2、基本题型（1）先入先出

滑动窗口

剑指 Offer II 041. 滑动窗口的平均值

剑指 Offer II 042. 最近请求次数 while（队首）

class RecentCounter {
    private Queue times;
    private int windowSize;

    public RecentCounter() {
        times = new LinkedList<>();
        windowSize = 3000;
    }

    public int ping(int t) {
        times.offer(t);
        while (times.peek() + windowSize < t){
            times.poll();
        }
        return times.size();
    }
}

（2）二叉树BFS

单队列+res

剑指 Offer II 043. 往完全二叉树添加节点

//bfs算法
public List bfs(TreeNode root) {
    Queue queue = new LinkedList<>();
    if (root != null) queue.offer(root);

    List result = new ArrayList<>();
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        result.add(node.val);

        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
    return result;
}

二叉搜索树模板

class CBTInserter {
    private Queue queue;
    private TreeNode root;


    public CBTInserter(TreeNode root) {
        this.root = root;

        queue = new LinkedList<>();

        queue.offer(root);

        while (queue.peek().left != null && queue.peek().right != null) {
            TreeNode node = queue.poll();
            queue.offer(node.left);
            queue.offer(node.right);
        }
    }

    public int insert(int v) {
        TreeNode parent = queue.peek();
        TreeNode node = new TreeNode(v);

        if(parent.left==null){
            parent.left = node;
        }else {
            parent.right = node;

            queue.poll();
            queue.offer(parent.left);
            queue.offer(parent.right);
        }
        return parent.val;
    }

    public TreeNode get_root() {
        return this.root;
    }
}

分层输出：计数法或者双队列交替法（加一个queue1是否为空的判断）
- 剑指 Offer II 044. 二叉树每层的最大值
- 计数法

//方法一：计数法
    public List largestValues(TreeNode root) {
        int curr = 0;
        int next = 0;

        Queue queue = new LinkedList<>();
        List result = new LinkedList<>();

        if (root != null) {
            queue.offer(root);
            curr++;
        }

        int max = Integer.MIN_VALUE;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            curr--;
            max = Math.max(max, node.val);

            if (node.left != null) {
                queue.offer(node.left);
                next++;
            }
            if (node.right != null) {
                queue.offer(node.right);
                next++;
            }

            if (curr == 0) {
                result.add(max);
                curr = next;
                max = Integer.MIN_VALUE;
                next = 0;
            }
        }
        return result;
    }

双队列交替法

//方法二：双队列交替
public List largestValues2(TreeNode root) {
    Queue queue1 = new LinkedList<>();
    Queue queue2 = new LinkedList<>();

    List result = new LinkedList<>();

    if(root!=null){
        queue1.offer(root);
    }

    int max = Integer.MIN_VALUE;

    while (!queue1.isEmpty()){
        TreeNode node = queue1.poll();
        max = Math.max(max,node.val);

        if (node.left != null) {
            queue2.offer(node.left);
        }
        if (node.right != null) {
            queue2.offer(node.right);
        }

        if (queue1.isEmpty()){
            queue1 = queue2;
            queue2 = new LinkedList<>();

            result.add(max);
            max = Integer.MIN_VALUE;
        }
    }
    return result;
}

剑指 Offer II 045. 二叉树最底层最左边的值每层第一个
剑指 Offer II 046. 二叉树的右侧视图每层最后一个

【剑指offer2】 chap7 队列

Java相关栏目本月热门文章