LeetCode 剑指 Offer II 队列 专题总结

云惠网小编 2022年1月15日09:18:05
评论
3102字阅读10分20秒
摘要

剑指 Offer || 队列专题总结,看完就能掌握二叉树和bfs广度优先搜索

广告也精彩
  • 二叉树的节点个数的范围是 [0,100]
  • -100 <= Node.val <= 100

LeetCode 剑指 Offer II 队列 专题总结
输入: [1,2,3,null,5,null,4]
输出: [1,3,4]

class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
if(root == nullptr) return {};
vector<int> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int n = q.size();
int right;
for(int i = 0; i < n; i++) {
TreeNode* node = q.front();
q.pop();
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
if(i == n - 1) right = node->val;
}
res.push_back(right);
}
return res;
}
};
  • 二叉树的节点个数的范围是 [1,104]
  • -231 <= Node.val <= 231 - 1

提示:

046. 二叉树的右侧视图

示例:

跟上一题基本一样,i == n-1 时取最右值

思路:

bfs模板
遍历每一层,保存最大值,然后将每一层加入队列

class Solution {
public:
int findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
int res;
while(!q.empty()) {
int n = q.size();
for(int i = 0; i < n; i++) {
TreeNode* node = q.front();
q.pop();
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
if(i == 0) res = node->val;
}
}
return res;
}
};
  • LeetCode 剑指 Offer II 链表 专题总结
  • LeetCode 剑指 Offer II 哈希表 专题总结
  • LeetCode 剑指 Offer II 栈 专题总结

题目:

043. 往完全二叉树添加节点(难一点)

  • 最初给定的树是完全二叉树,且包含 11000 个节点。
  • 每个测试用例最多调用 CBTInserter.insert 操作 10000 次。
  • 给定节点或插入节点的每个值都在 05000 之间。
class Solution {
public:
vector<int> largestValues(TreeNode* root) {
if(root == nullptr) return {};
vector<int> res;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()) {
int curMax = INT_MIN;
int n = q.size();
for(int i = 0; i < n; i++) {
TreeNode* node = q.front(); q.pop();
curMax = max(curMax, node->val);
if(node->left) q.push(node->left);
if(node->right) q.push(node->right);
}
res.push_back(curMax);
}
return res;
}
};

示例:

示例:

输入:inputs = [“CBTInserter”,“insert”,“insert”,“get_root”], inputs = [[[1,2,3,4,5,6]],[7],[8],[]]
输出:[null,3,4,[1,2,3,4,5,6,7,8]]

完全二叉树是每一层(除最后一层外)都是完全填充(即,节点数达到最大,第 n 层有 2n-1 个节点)的,并且所有的节点都尽可能地集中在左侧。
设计一个用完全二叉树初始化的数据结构 CBTInserter,它支持以下几种操作:

  • CBTInserter(TreeNode root) 使用根节点为 root 的给定树初始化该数据结构;
  • CBTInserter.insert(int v) 向树中插入一个新节点,节点类型为 TreeNode,值为 v 。使树保持完全二叉树的状态,并返回插入的新节点的父节点的值;
  • CBTInserter.get_root() 将返回树的根节点。

041. 滑动窗口的平均值

bfs模板 跟上题差不多,当i == 0 时取最左值

042. 最近请求次数

题目:
给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。

提示:

提示:

题目:

往期文章 :

这些都是这些都是模板题,结合二叉树,bfs套路,掌握第三道,第四道其他差不多都一样

  • 📚 博客主页:⭐️这是一只小逸白的博客鸭~⭐️
  • 👉 欢迎 关注❤️点赞👍收藏⭐️评论📝
  • 😜 小逸白正在备战实习,经常更新面试题LeetCode题解,欢迎志同道合的朋友互相交流~
  • 💙 若有问题请指正,记得关注哦,感谢~

给定一棵二叉树的根节点 root ,请找出该二叉树中每一层的最大值。

思路:

思路:

  • CBTInserter
  • 为了方便 insert,在队列中存放左右子节点未满的节点
  • insert
  • 直接访问队首,左为空插左节点;
  • 右为空插右节点,然后这是表示节点满了,将队首出队,左右两个节点插到队尾
  • get_root:直接返回全局变量的根节点

示例:

  • 二叉树的节点个数的范围是 [0,104]
  • -231 <= Node.val <= 231 - 1

题目:

思路:

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]
在这里插入图片描述

太简单了,略,感兴趣可以看看
题目:滑动窗口的平均值

目录

  • 041. 滑动窗口的平均值
  • 042. 最近请求次数
  • 043. 往完全二叉树添加节点(难一点)
  • 044. 二叉树每层的最大值(下面都是bfs模板)
  • 045. 二叉树最底层最左边的值
  • 046. 二叉树的右侧视图

044. 二叉树每层的最大值(下面都是bfs模板)

class CBTInserter {
public:
TreeNode* root;
queue<TreeNode*> q;
CBTInserter(TreeNode* root) {
this->root = root;
q.push(root);
//用队列存储左右节点左右子节点未满的节点
//[1,2,3,4,5,6] 存储3,4,5
while(q.front()->left && q.front()->right) {
q.push(q.front()->left);
q.push(q.front()->right);
q.pop();
}
}
int insert(int v) {
TreeNode* root = q.front();
TreeNode* node = new TreeNode(v);
if(root->left == nullptr) {
root->left = node;
}else if(root->right == nullptr) {
root->right = node;
//队列加入两个左右节点并去除根节点
q.push(root->left);
q.push(root->right);
q.pop();
}
return root->val;
}
TreeNode* get_root() {
return root;
}
};

太简单了,略,感兴趣可以看看
题目:最近请求次数

LeetCode 剑指 Offer II 队列 专题总结
输入: root = [2,1,3]
输出: 1

提示:

045. 二叉树最底层最左边的值

给定一个二叉树的 根节点 root,请找出该二叉树的 最底层 最左边 节点的值。
假设二叉树中至少有一个节点。

本文转自 https://blog.csdn.net/qq_45911678/article/details/122483310

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度 java

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论