剑指 Offer II 队列

041. 滑动窗口的平均值

Queue queue = new LinkedList();
循环队列实现

class MovingAverage {
        int hh=0,tt=0;
        double sum=0;
          int []q;
    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        q=new int [size];
    }
    //循环队列
    public double next(int val) {
        tt=(tt+1)%q.length;    
        if(hh==tt)
        {
            sum-=q[hh]; 
              hh=(hh+1)%q.length;
            sum+=q[tt]=val;
            return sum/q.length;
        }
        else   sum+=q[tt]=val;
        return sum/(tt-hh);
    
    }
}

042. 最近请求次数

class RecentCounter {
Queue queue;
    public RecentCounter() {
        queue = new LinkedList();

    }   
    public int ping(int t) {
          queue.offer(t);
          while(queue.peek()

class Solution {

    public List largestValues(TreeNode root) {
       
        Listans=new ArrayList<>();
         if(root==null)return ans;
        Queueq=new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty())
        {
            int n=q.size();
            int res=Integer.MIN_VALUE;
            for(int i=0;i

class Solution {
    int res=0,step=0;
    void dfs(TreeNode x,int depth)
    {
        if(depth>step)
        {
            step=depth;
            res=x.val;
        }
        TreeNode p=x.left;
        TreeNode q=x.right;
        if(p!=null)dfs(p,depth+1);
        if(q!=null)dfs(q,depth+1);

    }
    public int findBottomLeftValue(TreeNode root) {
      dfs(root,1);
      return res;
    }
}

class Solution {
    public int findBottomLeftValue(TreeNode root) {
       Queueq=new LinkedList<>();
       q.offer(root);
     int res=0;
      while(!q.isEmpty())
       { 
           res=q.peek().val;
           int n=q.size();
           for(int i=0;i

class Solution { 
    List ans=new ArrayList<>();
    public List rightSideView(TreeNode root) {
        if(root==null)return ans;
        Queue  q=new LinkedList<>();
        q.offer(root);
        while(!q.isEmpty())
        {
            int n=q.size();
            int temp=0;
            for(int i=0;i

class Solution {
    public TreeNode pruneTree(TreeNode root) {  
        if( root.left!=null) root.left= pruneTree(root.left);
        if(root.right!=null)root.right= pruneTree(root.right);
        if(root.val==0&&root.left==null&&root.right==null)root=null;
        return root;

    }
}