【LeetCode】七、树、堆、图
文章目录
- 1、树结构
- 2、二叉树
- 3、二叉树的遍历
- 4、堆结构(Heap)
- 5、堆化
- 6、图
1、树结构
节点、根节点、叶子节点:

高度、深度、层三者的示意图:

2、二叉树
相比其他树,二叉树即每个节点最多两个孩子(两个分支):

如下图:满二叉树一定是完全二叉树,完全二叉树却不一定是满二叉树

补充:上面对满二叉树的定义不准确,满二叉树还要满足:所有的叶子节点在同一层

以上这个,虽然满足:除了叶子节点,每个节点都有两个孩子,但不满足所有叶子节点都在同一层,因此不是满二叉树。
3、二叉树的遍历
- 前序遍历,即根节点在前:前左右
- 中序遍历,即根节点在中:左中右
- 后序遍历,即根节点在后:左右后

如下:整个树看成三块,A、A的左子树、A的右子树,在两块子树里,继续按中序的左根右遍历,结果就是:D ⇒ B ⇒ E ⇒ A ⇒ F ⇒ C ⇒ G


同理,如果下面还有,那就继续分:

一句话,从根节点入手,把整个树看成左、根、右三大块,按左根右中序遍历,左右每块子树里,按子树的根节点继续分成左、根、右三大块,每块子树里依旧按照左根右中序遍历
4、堆结构(Heap)
堆即一种二叉树:完全二叉树。前面提到完全二叉树即从上到下、从左到右依次填满的二叉树,即可以左上有节点而右下无节点(图A、B),但:
- 不能同一层左边无节点,但右边有节点(图C),这样不满足从左到右,不是完全二叉树
- 不能同一层,左边有节点,但右边无节点,但下一层左边又有节点(图D),这样不满足从上到下,不是完全二叉树

堆有两个特点:
- 首先得是一个完全二叉树
- 其次,每个节点 >= 其所有孩子节点 (最大堆),或, 每个节点 <= 其所有孩子节点 (最小堆)
对最大堆,堆顶元素是整个堆的最大值,对最小堆,堆顶元素是整个堆的最小值


堆的时间复杂度:

比如删除一个最小堆的根节点:

干掉1以后,把右下角的7放上来,先保持完全二叉树的结构:

再向下比较,把7放到该放的位置。这是个最小堆,因此,先将7和最小的孩子节点2交换:

又发现7比孩子节点4和5打,因此,再把7和最小的孩子节点4交换,删除完成:

5、堆化
堆化,即把一组无序的数加到堆里去。可先把一组数转成完全二叉树,再将完全二叉树调整为最大堆或者最小堆。
如下,一个数组转为一个完全二叉树,其结果是唯一的(遍历数组,从上到下、从左到右的摆放),即0号元素当根节点,后面两个1、2号元素当根节点的左右子节点,3、4、5、6号元素分别当1、2号元素所在节点的左右子节点

将这个二叉树转为最小堆,核心思想是:把每个节点和其孩子节点进行对比,看每个节点是否满足:值小于等于任何它的一个子节点,不满足时,则把该节点和其最小的孩子节点交换。
因为叶子节点没有子节点,所以从倒数第二层开始看:9和7两个节点,9符合条件,均小于其两个子节点,7则不符,因此,7和5交换:

交换完成,再往上看上一层:10 > 5 也 10 > 9,选更小的5这个节点交换:

同理,换完后,第二层不再满足最小堆,需要再交换,10 > 8 也有 10 > 7,选最小的7这个节点进行交换。
6、图
和树的父子关系相比,图则类似邻居关系。对于图,有一个度的概念(degree),如下,顶点上有两条边与其相连,该顶点的度为2

分类:

前面提到了顶点的度,对于有向图,则是:
- 入度:指向该顶点的边的数量
- 出度:从该顶点出发的边的数量
如下:丁节点,入度为2,出度为0

再说权重图:如下,求杭州到北京的最短路径

相关文章:
【LeetCode】七、树、堆、图
文章目录 1、树结构2、二叉树3、二叉树的遍历4、堆结构(Heap)5、堆化6、图 1、树结构 节点、根节点、叶子节点: 高度、深度、层三者的示意图: 2、二叉树 相比其他树,二叉树即每个节点最多两个孩子(两个分…...
FPGA PCIe加载提速方案
目录 1.bit流压缩 2.flash加载速度 3.Tandem模式 1.bit流压缩 set_property BITSTREAM.GENERAL.COMPRESS TRUE [current_design] 2.flash加载速度 打开bitstream setting,设置SPI的线宽和速率(线宽按原理图设置,速率尽可能高)…...
Hi3861 OpenHarmony嵌入式应用入门--轮询按键
本篇介绍使用轮询方式读取gpio状态来判断按键状态。 原理图如下 GPIO API API名称 说明 hi_u32 hi_gpio_init(hi_void); GPIO模块初始化 hi_u32 hi_io_set_pull(hi_io_name id, hi_io_pull val); 设置某个IO上下拉功能。 hi_u32 hi_gpio_set_dir(hi_gpio_idx id, hi_gpi…...
js,uni 自定义 时间选择器 vue2
<template><view class"reserve-time-box"><view class"title">选择时间</view><view class"date-box"><view class"date-scroll-box" :style"{ width : ${dataTimeWidth}rpx }"><v…...
搜索引擎的原理与相关知识
搜索引擎是一种网络服务,它通过互联网帮助用户找到所需的信息。搜索引擎的工作原理主要包括以下几个步骤: 网络爬虫(Web Crawler):搜索引擎使用网络爬虫(也称为蜘蛛或机器人)来遍历互联网&#…...
React:tabs或标签页自定义右击菜单内容,支持内嵌iframe关闭菜单方案
React:tabs或标签页自定义右击菜单内容,支持内嵌iframe关闭菜单方案 不管是react、vue还是原生js,原理是一样的。 注意如果内嵌iframe情况下,iframe无法使用事件监听,但是可以使用iframe的任何点击行为都会往父级wind…...
Taro +vue3 中的微信小程序中的分享
微信小程序 右上角分享 的触发 以及配 useShareAppMessage(() > {return {title: "电影属全国通兑券",page: /pages/home/index,imageUrl: "http:///chuanshuo.jpg",};}); 置 就是Taro框架中提供的一个分享Api 封装好的...
视频监控EasyCVR视频汇聚/智能边缘网关:EasySearch无法探测到服务器如何处理?
安防监控EasyCVR智能边缘网关/视频汇聚网关/视频网关属于软硬一体的边缘计算硬件,可提供多协议(RTSP/RTMP/国标GB28181/GAT1400/海康Ehome/大华/海康/宇视等SDK)的设备接入、音视频采集、视频转码、处理、分发等服务,系统具备实时…...
openlayer 鼠标点击船舶,打开船舶简单弹框
背景: 对创建的地图对象,可以添加上监听事件,常用的有:地图点击事件、鼠标移动事件。 通过监听这些事件,又可以区分不同图层的不同要素,获取不同数据; 根据这些数据,又可以发起网络请…...
数据挖掘常见算法(关联)
Apriori算法 Apriori算法基于频繁项集性质的先验知识,使用由下至上逐层搜索的迭代方法,即从频繁1项集开始,采用频繁k项集搜索频繁k1项集,直到不能找到包含更多项的频繁项集为止。 Apriori算法由以下步骤组成,其中的核…...
vue项目集成CanvasEditor实现Word在线编辑器
CanvasEditor实现Word在线编辑器 官网文档:https://hufe.club/canvas-editor-docs/guide/schema.html 源码地址:https://github.com/Hufe921/canvas-editor 前提声明: 由于CanvasEditor目前不支持vue、react 等框架开箱即用版,所以…...
Redis Stream Redisson Stream
目录 一、Redis Stream1.1 场景1:多个客户端可以同时接收到消息1.1.1 XADD - 向stream添加Entry(发消息 )1.1.2 XREAD - 从stream中读取Entry(收消息)1.1.3 XRANGE - 从stream指定区间读取Entry(收消息&…...
threadX netx 设置IP地址以及获取IP地址
ThreadX 是一个实时操作系统(RTOS)内核,而 NetX 则是 Express Logic 提供的一个嵌入式 TCP/IP 网络栈,它经常与 ThreadX 一起使用来提供网络功能。在 ThreadX 和 NetX 中设置和获取 IP 地址通常涉及几个步骤。 设置 IP 地址 初始…...
计算机毕业设计hadoop+spark+hive知识图谱医生推荐系统 医生数据分析可视化大屏 医生爬虫 医疗可视化 医生大数据 机器学习 大数据毕业设计
测试过程及结果 本次对于医生推荐系统测试通过手动测试的方式共进行了两轮测试。 (1)第一轮测试中执行了个20个测试用例,通过16个,失败4个,其中属于严重缺陷的1个,属于一般缺陷的3个。 (2&am…...
lammps已经运算结束,有数据忘记算:rerun 命令
需要的文件 1、模拟运算的所有文件(模型 、in文件、力场文件) 2、模拟计算所得到的dump文件(原子轨迹文件) rerun命令的使用(修改in文件) 1、删除or注释掉 输出dump文件的那一行命令 2、加上需要补充计…...
CARLA自动驾驶模拟器基础
CARLA 使用服务器-客户端架构运行,其中 CARLA 服务器运行模拟并由客户端向其发送指令。客户端代码使用 API 与服务器进行通信。要使用 Python API,您必须通过 PIP 安装该模块: pip3 install carla-simulator # Python 3World and client 客…...
华为HCIP Datacom H12-821 卷16
1.判断题 在 VRRP 中,当设备状态变为 Master 后,,会立刻发送免费 ARP 来刷新下游设备的 MAC 表项,从而把用户的流量引到此台设备上来 A、对 B、错 正确答案: A 解析: 2.判断题 路由选择工具 route- policy 能够基于预先定义的条件来进行过滤并设置 BGP...
Python学习打卡:day17
day17 笔记来源于:黑马程序员python教程,8天python从入门到精通,学python看这套就够了 目录 day17121、Python 操作 MySQL 基础使用pymysql创建到 MySQL 的数据库链接执行 SQL 语句执行非查询性质的SQL语句执行查询性质的SQL语句 122、Pyth…...
Spring Cloud Gateway 与 Nacos 的完美结合
在现代微服务架构中,服务网关扮演着至关重要的角色。它不仅负责路由请求到相应的服务,还承担着诸如负载均衡、安全认证、限流熔断等重要功能。Spring Cloud Gateway 作为 Spring Cloud 生态系统中的一员,以其强大的功能和灵活的配置ÿ…...
vue2 element ui 表单 动态增加表单项 表单项值不可重复 select多选
案例 <template><el-form :model"form" ref"form" label-width"70px"><el-form-item><el-button icon"el-icon-plus" type"primary" plain click"add">新增</el-button><el-b…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
python报错No module named ‘tensorflow.keras‘
是由于不同版本的tensorflow下的keras所在的路径不同,结合所安装的tensorflow的目录结构修改from语句即可。 原语句: from tensorflow.keras.layers import Conv1D, MaxPooling1D, LSTM, Dense 修改后: from tensorflow.python.keras.lay…...
管理学院权限管理系统开发总结
文章目录 🎓 管理学院权限管理系统开发总结 - 现代化Web应用实践之路📝 项目概述🏗️ 技术架构设计后端技术栈前端技术栈 💡 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 🗄️ 数据库设…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
【JVM面试篇】高频八股汇总——类加载和类加载器
目录 1. 讲一下类加载过程? 2. Java创建对象的过程? 3. 对象的生命周期? 4. 类加载器有哪些? 5. 双亲委派模型的作用(好处)? 6. 讲一下类的加载和双亲委派原则? 7. 双亲委派模…...
