当前位置: 首页 > news >正文

力扣刷题(DAY09-DAY11)

Day09

0958. 二叉树的完全性检验

知识点:完全二叉树:在一棵完全二叉树中,除了最后一层外,所有层都被完全填满,并且最后一层中的所有节点都尽可能靠左。最后一层(第 h 层)中可以包含 1 到 2^{h}个节点,

当最后一层全部都满( 2^{h}个节点)的时候,就称为满二叉树。

题目大意:给你一棵二叉树的根节点 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. 二叉树的完全性检验 知识点&#xff1a;完全二叉树&#xff1a;在一棵完全二叉树中&#xff0c;除了最后一层外&#xff0c;所有层都被完全填满&#xff0c;并且最后一层中的所有节点都尽可能靠左。最后一层&#xff08;第 h 层&#xff09;中可以包含 1 到 个节点…...

IPC之管道

什么是管道&#xff1f; 管道的本质是操作系统在内核中创建出的一块缓冲区&#xff0c;也就是内存 管道的应用 $ ps aux | grep xxx ps aux 的标准输出写到管道&#xff0c;grep 从管道这块内存中读取数据来作为它的一个标准输入&#xff0c;而且 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

找了半天找不到,为什么国内文章环境是真的差&#xff0c; redis 集群不支持事务&#xff0c;而你的方法上面估计使用了 spring 的事务导致错误具体解决&#xff1a; Transactional(propagation Propagation.NOT_SUPPORTED)public <T> void removeMultiCacheMapValue…...

AVP-SLAM:自动泊车系统中的语义SLAM_

AVP-SLAM&#xff1a;自动泊车系统中的语义SLAM 附赠最强自动驾驶学习资料&#xff1a;直达链接 ●论文摘要 在自动代客泊车系统中车辆在狭窄且拥挤且没有GPS信号的停车场中进行导航&#xff0c;具备准确的定位能力是至关重要的。传统的基于视觉的方法由于在停车场中由于缺少…...

PHP反序列化--pop链

目录 一、了解pop链 1、pop链&#xff1a; 2、pop链触发规则&#xff1a; &#xff08;1&#xff09;通过普通函数触发&#xff1a; &#xff08;2&#xff09;通过魔术方法触发&#xff1a; 3、pop链魔术方法例题&#xff1a; 一、了解pop链 1、pop链&#xff1a; pop链…...

单片机中的几种周期(振动/时钟,状态,机械,指令周期)表示的含义(51为例)

几种周期含义及个人理解描述 参考&#xff1a;短文&#xff0c;参考&#xff0c;百度 个人理解简述&#xff1a;对于几个周期性来说&#xff0c;可以认为是小单位的时间组合成了长时间。就像把一个数据赋值&#xff0c;这个是简单的一个机械周期能完成的动作&#xff0c;但需要…...

Spring Boot+Vue前后端分离项目如何部署到服务器

&#x1f31f; 前言 欢迎来到我的技术小宇宙&#xff01;&#x1f30c; 这里不仅是我记录技术点滴的后花园&#xff0c;也是我分享学习心得和项目经验的乐园。&#x1f4da; 无论你是技术小白还是资深大牛&#xff0c;这里总有一些内容能触动你的好奇心。&#x1f50d; &#x…...

【学习总结】Ubuntu中vscode用ROS插件调试C++程序

1、教程 参考博客&#xff1a; 【ROS】 在VScode中 ROS Debug 配置方法非常详细版 关于launch文件的配置&#xff1a; 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的本质是一个项目管理工具&#xff0c;将项目开发过程抽象成一个项目对象模型&#xff08;POM&…...

Spring Boot(六十八):SpringBoot 整合Apache tika 实现文档内容解析

1 Apache Tika 介绍 Apache Tika 是一个开源的内容检测和分析框架,由Apache软件基金会开发和维护的顶级项目。它可以从各种格式的文件中提取元数据和文本内容。Tika非常适合处理全文搜索、内容分析、翻译、内容提取等需要大量处理和分析文档内容的任务。Apache Tika提供了多种…...

jQuery+CSS3自动轮播焦点图特效源码

jQueryCSS3自动轮播焦点图特效源码&#xff0c;源码由HTMLCSSJS组成&#xff0c;双击html文件可以本地运行效果&#xff0c;也可以上传到服务器里面 下载地址 jQueryCSS3自动轮播焦点图特效源码...

面试经典150题(114-118)

leetcode 150道题 计划花两个月时候刷完之未完成后转&#xff0c;今天完成了5道(114-118)150 gap 了一周&#xff0c;以后就不记录时间了。。 114.(70. 爬楼梯) 题目描述&#xff1a; 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不…...

HTML表单标签详解:如何用HTML标签打造互动网页?

在互联网的世界中&#xff0c;表单是用户与网站进行互动的重要桥梁。无论是注册新账号、提交反馈、还是在线购物&#xff0c;表单都扮演着至关重要的角色。在网页中&#xff0c;我们需要跟用户进行交互&#xff0c;收集用户资料&#xff0c;此时就需要用到表单标签。 HTML提供…...

Web 服务器-Tomcat

文章目录 Web服务器一、Tomcat简介二、基本使用三、在IDEA中创建Maven Web项目四、在IDEA中使用Tomcat Web服务器 一、Tomcat简介 二、基本使用 三、在IDEA中创建Maven Web项目 四、在IDEA中使用Tomcat...

(德迅零域)微隔离安全平台是什么,有什么作用?

网络隔离并不是新的概念&#xff0c;而微隔离技术&#xff08;Micro-Segmentation&#xff09;是VMware在应对虚拟化隔离技术时提出来的&#xff0c;但真正让微隔离备受大家关注是从2016年起连续3年微隔离技术都进入Gartner年度安全技术榜单开始。在2016年的Gartner安全与风险管…...

这些问题,每年软考报名时都有人问

​​软考报名实行网上在线报名的方式&#xff0c;每次在报名期间&#xff0c;考生都会遇到各种各样的问题&#xff0c;本文挑选了一些大家问的比较多的问题进行了解答&#xff0c;希望对大家有所帮助。 1、软考报名资格审核要审核多久&#xff1f; 一般来说审核时间在3个工作…...

JavaScript爬虫进阶攻略:从网页采集到数据可视化

在当今数字化世界中&#xff0c;数据是至关重要的资产&#xff0c;而网页则是一个巨大的数据源。JavaScript作为一种强大的前端编程语言&#xff0c;不仅能够为网页增添交互性&#xff0c;还可以用于网页爬取和数据处理。本文将带你深入探索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的下载链接吧&#xff0c;应该下一个就可以 4、运行结果部分展示 5、需要用到的图片要放在代码同一文件夹下 6、代码地址&#xff08;里面有需要用到的图片&#xff09; 1、游戏介绍和规则 规则如…...

png格式怎么转成gif?一个小窍门快速转换

如何将png转换成gif动画&#xff1f;作为新媒体工作者&#xff0c;在日常办公中少不了使用到gif格式图片。那么&#xff0c;当我们遇到需要将png格式转换成gif格式的时候要怎么操作呢&#xff1f;很简单&#xff0c;使用gif动画图片&#xff08;https://www.gif.cn/&#xff09…...

mysql笔记:20. 什么是数据库六大范式

文章目录 简介什么是范式最常用的范式 第一范式 - 1NF第二范式 - 2NF第三范式 - 3NF第四范式 - 4NF第五范式 - 5NF巴斯-科德范式 - BCNF总结 简介 什么是范式 范式&#xff08;Normal Form&#xff0c;简称NF&#xff09;是数据库设计时遵循的一种规范&#xff0c;不同的规范…...

4.GetMapping和PostMapping 和 @RequestMapping的区别。RequestBody 和ResponseBody的区别

1.GetMapping和PostMapping 和 RequestMapping的区别 //GetMapping只能通过get请求。 public class Hello1{GetMapping("hello1")public String h1(){return "1";}//PostMapping只能通过post请求&#xff0c;需要输入参数。 public class Hello2{PostMapp…...

UE要收费?难道ue的使用成本要增加吗?

去年&#xff0c;Epic Games在裁员16%后&#xff0c;放出要对非游戏制作等行业使用UE进行收费的消息。3月12日&#xff0c;Epic Games正式宣布了对UE、实时可视化工具Twinmotio和摄影测量应用RealityCapture的新定价。 Epic Games将从下个月开始推出新的Unreal订阅模式&#x…...

深度学习-2.6在MINST-FASHION上实现神经网络的学习流程

文章目录 在MINST-FASHION上实现神经网络的学习流程1. 导库2. 导入数据&#xff0c;分割小批量3. 定义神经网络4.定义训练函数5.进行训练与评估 在MINST-FASHION上实现神经网络的学习流程 现在我们要整合本节课中所有的代码实现一个完整的训练流程。 首先要梳理一下整个流程&a…...

Java后端八股----JVM篇

上图中线程1&#xff0c;2如果资源被抢占了&#xff0c;则程序计数器记录一下执行的行号&#xff0c;等到资源就绪后会从记录的行号继续向后执行。 Java8把静态变量以及常量放到了线程的本地内存原空间中(避免放在堆中不可控)。 &#x1f446;图中第二种情况不太容易出现…...

使用 C 或 C++ 扩展 Python

如果你会用 C&#xff0c;添加新的 Python 内置模块会很简单。以下两件不能用 Python 直接做的事&#xff0c;可以通过 extension modules 来实现&#xff1a;实现新的内置对象类型&#xff1b;调用 C 的库函数和系统调用。 为了支持扩展&#xff0c;Python API&#xff08;应…...

MVC接收请求教程

mvc接收各种请求 1-环境搭建 1.1-准备apifox发送请求 1.2-项目搭建 ①创建Web骨架的Maven项目 ​ --打开2023-IDEA &#xff0c;选择New Project ​ --选择Maven Archetype ​ --注意点&#xff1a;Catalog默认就行了 ​ --Archetype选择webapp ​ --JDK跟着黑马敲最好…...

宝鸡网站建设天伟网络/百度推广登录入口下载

Rsync文件同步的核心算法 文章出处:http://coolshell.cn/articles/7425.html#more-7425 rsync是unix/linux下同步文件的一个高效算法&#xff0c;它能同步更新两处计算机的文件与目录&#xff0c;并适当利用查找文件中的不同块以减少数据传输。rsync中一项与其他大部分类似程序…...

作图软件app/seo服务内容

本文内容参考自《操作系统概念第七版》、《操作系统精髓与设计原理 原书第六版》 前言为了解决外部碎片问题&#xff0c;一种可行的方案是允许物理地址空间为非连续的&#xff0c;具体的实现技术包括&#xff1a;分页、分段以及两者的合并段页式管理页式实现分页的基本方法涉及…...

新疆手机网站建设/搜索引擎优化岗位

近日&#xff0c;开始使用asp.net 2.0 的GridView。为了将长日期格式使用 DataFormatString 属性格式化为短日期显示方式&#xff0c;在网上找了些资料&#xff0c;开始时&#xff0c;按照我搜索到的文章的说明&#xff0c;设置DataFormatString"{0:yyyy-mm- dd}"&am…...

自己免费做网站有什么用/站长之家ping

相信很多人像我一样在学习python&#xff0c;pandas过程中对数据的选取和修改有很大的困惑(也许是深受Matlab)的影响。。。到今天终于完全搞清楚了&#xff01;&#xff01;&#xff01;先手工生出一个数据框吧import numpy as npimport pandas as pddf pd.DataFrame(np.arang…...

创建网站的好处/企业网站管理系统源码

线上集群目前使用的hadoop版本是CDH4.3.0,已经发生过两次jt的oom异常了&#xff0c;严重影响了线上作业的运行。刚开始的时候&#xff0c;通过减小retirejob的cacheSize和interval来减小jt的堆内存占用&#xff0c;起到了一定的效果&#xff0c;但其实也就是延长了jt宕掉的时间…...

建筑挂靠十大网站/360营销平台

描述&#xff1a;有一个会员表&#xff0c;有个birthday字段&#xff0c;值为YYYY-MM-DD格式&#xff0c;现在要查询一个时间段内过生日的会员&#xff0c;比如06-03到07-08这个时间段内所有过生日的会员。SQL语句&#xff1a; Select * From user Where date_format(birthday,…...