力扣刷题(DAY09-DAY11)
Day09
0958. 二叉树的完全性检验
知识点:完全二叉树:在一棵完全二叉树中,除了最后一层外,所有层都被完全填满,并且最后一层中的所有节点都尽可能靠左。最后一层(第
h
层)中可以包含1
到 个节点,当最后一层全部都满( 个节点)的时候,就称为满二叉树。
题目大意:给你一棵二叉树的根节点 root
,请你判断这棵树是否是一棵 完全二叉树 。
思路:尝试用层次遍历解决,如果存在上一个节点出队没有左孩子,但有右孩子,就是flase;
或者本节点都没有,但下一个有。可以设置bool will来判断 再深入思考一下,在遍历到当前节点的时候 ,前面如果已经出现过空节点,那他一定不是完全二叉树。
于是:层次遍历二叉树,无论节点是否存在,都放入队列中,当出现空节点的时候标记一下;继续遍历,如果后面还有结点,说明不是完全二叉树
其实也可以说完全二叉树,层次遍历到最后一个节点时一定不会出现空节点
class Solution {
public:bool isCompleteTree(TreeNode* root) {// 层次遍历bool will = 0;queue<TreeNode*> q;TreeNode* visited;q.push(root);while (!q.empty()) {visited = q.front();q.pop();if (visited == NULL) {will = 1; // 空节点} else {if (will) // 前面有一个空return false;q.push(visited->left);q.push(visited->right);}}return true;}
};
这里强调说明一下:
visited = q.front(); 一定要放在前面写
0543. 二叉树的直径
题目要求:
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root
。两节点之间路径的 长度 由它们之间边数表示。
思路:长度最长的路线应该是从左边的最高高度到右边的最高高度;根据边计算一下,应该是左hight+右hight-1---》左子树高度+柚子树高度;
好好好,按着这样写下去,出现这个情况了……
树大概张这个样子
重新想思路:犯错原因只考虑了焦点在根节点的情况,
于是升级版:递归地计算每个节点的左子树和右子树的深度,并在遍历的过程中更新最大直径,最终得到整棵树的直径。
max_len=max(height(vistied->left)+height(vistied->right),max_len) ;
//visited 每个结点,用中序遍历一下吧;
于是代码就有了:
class Solution {
public:int max_len=0;int height(TreeNode* root){//求高度if(!root) return 0;return max(height(root->left),height(root->right))+1;}void inorder(TreeNode* root){//每个结点,用中序遍历一下吧;if(!root) return;inorder(root->left);max_len=max(height(root->left)+height(root->right),max_len) ;inorder(root->right);}int diameterOfBinaryTree(TreeNode* root) {if(!root) return 0;inorder(root);return max_len;}
};
思路有了,不放在优化一下
class Solution {
public:int diameterOfBinaryTree(TreeNode* root) {int maxDiameter = 0;maxDepth(root, maxDiameter);return maxDiameter;}int maxDepth(TreeNode* node, int& maxDiameter) {if (node == nullptr) {return 0;}int leftDepth = maxDepth(node->left, maxDiameter);int rightDepth = maxDepth(node->right, maxDiameter);maxDiameter = max(maxDiameter, leftDepth + rightDepth);return 1 + max(leftDepth, rightDepth);}
};
0662. 二叉树最大宽度
题目大意:
给你一棵二叉树的根节点 root
,返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点(即,两个端点)之间的长度。将这个二叉树视作与满二叉树结构相同,两端点间会出现一些延伸到这一层的 null
节点,这些 null
节点也计入长度。
想到一种这个情况,测试结果为4;
思路:求层的宽度,当然是层次遍历bfs啦,那怎么保证左孩子不存在,右孩子还能存进去的?
还记得树的顺序存储么?用这个就好。left_index=双亲*2;right_index=双亲*2+1;
这样我们层次遍历是,可以建立二维队列
queue<pair<TreeNode*, unsigned long long>> q;
为什么unsigned longlong 呢? 因为题目所给的数据范围是3000个节点,如果没层一个节点且都靠右排列,那么会有1000多层的树。 这样导致在树底部的节点编号为2的一千多次方。而这个范围在多数语言中都是没办法正常处理的。
class Solution {
public:int widthOfBinaryTree(TreeNode* root) {if (!root) return 0;int max_width = 0;queue<pair<TreeNode*, unsigned long long>> q;q.push({root, 1});while (!q.empty()) {int size = q.size();unsigned long long leftmost = q.front().second;unsigned long long rightmost = leftmost;for (int i = 0; i < size; i++) {auto [node, index] = q.front();q.pop();if (i == 0) {leftmost = index;}if (i == size - 1) {rightmost = index;}if (node->left) {q.push({node->left, 2 * index});}if (node->right) {q.push({node->right, 2 * index + 1});}}max_width = max(static_cast<int>(rightmost - leftmost + 1), max_width);}return max_width;}
};
好了,今天就到这里 over
相关文章:
力扣刷题(DAY09-DAY11)
Day09 0958. 二叉树的完全性检验 知识点:完全二叉树:在一棵完全二叉树中,除了最后一层外,所有层都被完全填满,并且最后一层中的所有节点都尽可能靠左。最后一层(第 h 层)中可以包含 1 到 个节点…...
IPC之管道
什么是管道? 管道的本质是操作系统在内核中创建出的一块缓冲区,也就是内存 管道的应用 $ ps aux | grep xxx ps aux 的标准输出写到管道,grep 从管道这块内存中读取数据来作为它的一个标准输入,而且 ps 和 grep 之间是兄弟关系&a…...
VUE-组件间通信(二)$emit
$emit 1、单向绑定 子组件向父组件传值 2、使用示例 父组件 <template><div id"app"><!-- 监听自定义触发事件 emitInvokeEvents--><SonDemo emitInvokeEvents"fatherFunction"></SonDemo></div> </template&…...
java 程序连接 redis 集群 的时候报错 MUTLI is currently not supported in cluster mode
找了半天找不到,为什么国内文章环境是真的差, redis 集群不支持事务,而你的方法上面估计使用了 spring 的事务导致错误具体解决: Transactional(propagation Propagation.NOT_SUPPORTED)public <T> void removeMultiCacheMapValue…...
AVP-SLAM:自动泊车系统中的语义SLAM_
AVP-SLAM:自动泊车系统中的语义SLAM 附赠最强自动驾驶学习资料:直达链接 ●论文摘要 在自动代客泊车系统中车辆在狭窄且拥挤且没有GPS信号的停车场中进行导航,具备准确的定位能力是至关重要的。传统的基于视觉的方法由于在停车场中由于缺少…...
PHP反序列化--pop链
目录 一、了解pop链 1、pop链: 2、pop链触发规则: (1)通过普通函数触发: (2)通过魔术方法触发: 3、pop链魔术方法例题: 一、了解pop链 1、pop链: pop链…...
单片机中的几种周期(振动/时钟,状态,机械,指令周期)表示的含义(51为例)
几种周期含义及个人理解描述 参考:短文,参考,百度 个人理解简述:对于几个周期性来说,可以认为是小单位的时间组合成了长时间。就像把一个数据赋值,这个是简单的一个机械周期能完成的动作,但需要…...
Spring Boot+Vue前后端分离项目如何部署到服务器
🌟 前言 欢迎来到我的技术小宇宙!🌌 这里不仅是我记录技术点滴的后花园,也是我分享学习心得和项目经验的乐园。📚 无论你是技术小白还是资深大牛,这里总有一些内容能触动你的好奇心。🔍 &#x…...
【学习总结】Ubuntu中vscode用ROS插件调试C++程序
1、教程 参考博客: 【ROS】 在VScode中 ROS Debug 配置方法非常详细版 关于launch文件的配置: launch.json {"version": "0.2.0","configurations": [{"name": "ROS: Launch","request"…...
html--蝴蝶
<!DOCTYPE html> <html lang"en" > <head> <meta charset"UTF-8"> <title>蝴蝶飞舞</title> <link rel"stylesheet" href"https://cdnjs.cloudflare.com/ajax/libs/meyer-reset/2.0/reset.min.cs…...
线程的 sleep()方法和 yield()方法有什么区别?为什么 Thread 类的 sleep()和 yield ()方法是静态的?
该文章专注于面试,面试只要回答关键点即可,不需要对框架有非常深入的回答,如果你想应付面试,是足够了,抓住关键点 线程的 sleep()方法和 yield()方法有什么区别 sleep()方法: sleep()方法使当前线程进入休眠状态,即暂停执行一段时间。它是静态方法,属于Thread类,调用…...
Java进阶 Maven基础
资料格式 配置文件 com.itheima Java代码 Statement stat con.createStatement(); 示例 com.itheima 命令 mvn test - Maven简介 传统项目管理状态分析 Maven 是什么 Maven的本质是一个项目管理工具,将项目开发过程抽象成一个项目对象模型(POM&…...
Spring Boot(六十八):SpringBoot 整合Apache tika 实现文档内容解析
1 Apache Tika 介绍 Apache Tika 是一个开源的内容检测和分析框架,由Apache软件基金会开发和维护的顶级项目。它可以从各种格式的文件中提取元数据和文本内容。Tika非常适合处理全文搜索、内容分析、翻译、内容提取等需要大量处理和分析文档内容的任务。Apache Tika提供了多种…...
jQuery+CSS3自动轮播焦点图特效源码
jQueryCSS3自动轮播焦点图特效源码,源码由HTMLCSSJS组成,双击html文件可以本地运行效果,也可以上传到服务器里面 下载地址 jQueryCSS3自动轮播焦点图特效源码...
面试经典150题(114-118)
leetcode 150道题 计划花两个月时候刷完之未完成后转,今天完成了5道(114-118)150 gap 了一周,以后就不记录时间了。。 114.(70. 爬楼梯) 题目描述: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不…...
HTML表单标签详解:如何用HTML标签打造互动网页?
在互联网的世界中,表单是用户与网站进行互动的重要桥梁。无论是注册新账号、提交反馈、还是在线购物,表单都扮演着至关重要的角色。在网页中,我们需要跟用户进行交互,收集用户资料,此时就需要用到表单标签。 HTML提供…...
Web 服务器-Tomcat
文章目录 Web服务器一、Tomcat简介二、基本使用三、在IDEA中创建Maven Web项目四、在IDEA中使用Tomcat Web服务器 一、Tomcat简介 二、基本使用 三、在IDEA中创建Maven Web项目 四、在IDEA中使用Tomcat...
(德迅零域)微隔离安全平台是什么,有什么作用?
网络隔离并不是新的概念,而微隔离技术(Micro-Segmentation)是VMware在应对虚拟化隔离技术时提出来的,但真正让微隔离备受大家关注是从2016年起连续3年微隔离技术都进入Gartner年度安全技术榜单开始。在2016年的Gartner安全与风险管…...
这些问题,每年软考报名时都有人问
软考报名实行网上在线报名的方式,每次在报名期间,考生都会遇到各种各样的问题,本文挑选了一些大家问的比较多的问题进行了解答,希望对大家有所帮助。 1、软考报名资格审核要审核多久? 一般来说审核时间在3个工作…...
JavaScript爬虫进阶攻略:从网页采集到数据可视化
在当今数字化世界中,数据是至关重要的资产,而网页则是一个巨大的数据源。JavaScript作为一种强大的前端编程语言,不仅能够为网页增添交互性,还可以用于网页爬取和数据处理。本文将带你深入探索JavaScript爬虫技术的进阶应用&#…...
MATLAB教程
目录 前言一、MATLAB基本操作1.1 界面简介1.2 搜索路径1.3 交互式命令操作1.4 帮助系统 二、MATLAB语言基础2.1 数据类型2.2 MATLAB运算2.2.1 算数运算2.2.2 关系运算2.2.3 逻辑运算 2.3 常用内部函数2.4 结构数据与单元数据 三、MATLAB程序设计3.1 M文件3.2 函数文件3.3 程序控…...
爱恩斯坦棋小游戏使用C语言+ege/easyx实现
目录 1、游戏介绍和规则 2、需要用到的头文件 3、这里我也配上一个ege和easyx的下载链接吧,应该下一个就可以 4、运行结果部分展示 5、需要用到的图片要放在代码同一文件夹下 6、代码地址(里面有需要用到的图片) 1、游戏介绍和规则 规则如…...
png格式怎么转成gif?一个小窍门快速转换
如何将png转换成gif动画?作为新媒体工作者,在日常办公中少不了使用到gif格式图片。那么,当我们遇到需要将png格式转换成gif格式的时候要怎么操作呢?很简单,使用gif动画图片(https://www.gif.cn/)…...
mysql笔记:20. 什么是数据库六大范式
文章目录 简介什么是范式最常用的范式 第一范式 - 1NF第二范式 - 2NF第三范式 - 3NF第四范式 - 4NF第五范式 - 5NF巴斯-科德范式 - BCNF总结 简介 什么是范式 范式(Normal Form,简称NF)是数据库设计时遵循的一种规范,不同的规范…...
4.GetMapping和PostMapping 和 @RequestMapping的区别。RequestBody 和ResponseBody的区别
1.GetMapping和PostMapping 和 RequestMapping的区别 //GetMapping只能通过get请求。 public class Hello1{GetMapping("hello1")public String h1(){return "1";}//PostMapping只能通过post请求,需要输入参数。 public class Hello2{PostMapp…...
UE要收费?难道ue的使用成本要增加吗?
去年,Epic Games在裁员16%后,放出要对非游戏制作等行业使用UE进行收费的消息。3月12日,Epic Games正式宣布了对UE、实时可视化工具Twinmotio和摄影测量应用RealityCapture的新定价。 Epic Games将从下个月开始推出新的Unreal订阅模式&#x…...
深度学习-2.6在MINST-FASHION上实现神经网络的学习流程
文章目录 在MINST-FASHION上实现神经网络的学习流程1. 导库2. 导入数据,分割小批量3. 定义神经网络4.定义训练函数5.进行训练与评估 在MINST-FASHION上实现神经网络的学习流程 现在我们要整合本节课中所有的代码实现一个完整的训练流程。 首先要梳理一下整个流程&a…...
Java后端八股----JVM篇
上图中线程1,2如果资源被抢占了,则程序计数器记录一下执行的行号,等到资源就绪后会从记录的行号继续向后执行。 Java8把静态变量以及常量放到了线程的本地内存原空间中(避免放在堆中不可控)。 👆图中第二种情况不太容易出现…...
使用 C 或 C++ 扩展 Python
如果你会用 C,添加新的 Python 内置模块会很简单。以下两件不能用 Python 直接做的事,可以通过 extension modules 来实现:实现新的内置对象类型;调用 C 的库函数和系统调用。 为了支持扩展,Python API(应…...
MVC接收请求教程
mvc接收各种请求 1-环境搭建 1.1-准备apifox发送请求 1.2-项目搭建 ①创建Web骨架的Maven项目 --打开2023-IDEA ,选择New Project --选择Maven Archetype --注意点:Catalog默认就行了 --Archetype选择webapp --JDK跟着黑马敲最好…...
宝鸡网站建设天伟网络/百度推广登录入口下载
Rsync文件同步的核心算法 文章出处:http://coolshell.cn/articles/7425.html#more-7425 rsync是unix/linux下同步文件的一个高效算法,它能同步更新两处计算机的文件与目录,并适当利用查找文件中的不同块以减少数据传输。rsync中一项与其他大部分类似程序…...
作图软件app/seo服务内容
本文内容参考自《操作系统概念第七版》、《操作系统精髓与设计原理 原书第六版》 前言为了解决外部碎片问题,一种可行的方案是允许物理地址空间为非连续的,具体的实现技术包括:分页、分段以及两者的合并段页式管理页式实现分页的基本方法涉及…...
新疆手机网站建设/搜索引擎优化岗位
近日,开始使用asp.net 2.0 的GridView。为了将长日期格式使用 DataFormatString 属性格式化为短日期显示方式,在网上找了些资料,开始时,按照我搜索到的文章的说明,设置DataFormatString"{0:yyyy-mm- dd}"&am…...
自己免费做网站有什么用/站长之家ping
相信很多人像我一样在学习python,pandas过程中对数据的选取和修改有很大的困惑(也许是深受Matlab)的影响。。。到今天终于完全搞清楚了!!!先手工生出一个数据框吧import numpy as npimport pandas as pddf pd.DataFrame(np.arang…...
创建网站的好处/企业网站管理系统源码
线上集群目前使用的hadoop版本是CDH4.3.0,已经发生过两次jt的oom异常了,严重影响了线上作业的运行。刚开始的时候,通过减小retirejob的cacheSize和interval来减小jt的堆内存占用,起到了一定的效果,但其实也就是延长了jt宕掉的时间…...
建筑挂靠十大网站/360营销平台
描述:有一个会员表,有个birthday字段,值为YYYY-MM-DD格式,现在要查询一个时间段内过生日的会员,比如06-03到07-08这个时间段内所有过生日的会员。SQL语句: Select * From user Where date_format(birthday,…...