二叉树part6 | ● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98.验证二叉搜索树
文章目录
- 654.最大二叉树
- 思路
- 代码
- 617.合并二叉树
- 思路
- 代码
- 700.二叉搜索树中的搜索
- 思路
- 代码
- 98.验证二叉搜索树
- 思路
- 官方题解
- 代码
- 困难
- 今日收获
654.最大二叉树
思路
前序遍历构造二叉树。
找出数组中最大值,然后递归处理左右子数组。
时间复杂度On2
空间复杂度On
代码
func constructMaximumBinaryTree(nums []int) *TreeNode {imap:=make(map[int]int)for k,v:=range nums{imap[v]=k}res:=&TreeNode{}var build func(node *TreeNode,l,r int)build = func(node *TreeNode,l,r int){root:=max(nums[l:r+1])index:=imap[root]node.Val=rootif index>l{node.Left=&TreeNode{}build(node.Left,l,index-1)}if index<r{node.Right=&TreeNode{}build(node.Right,index+1,r)}}build(res,0,len(nums)-1)return res
}func max(s []int)int{res:=0for i:=0;i<len(s);i++{if res<s[i]{res=s[i]}}return res
}
617.合并二叉树
思路
递归构建。
目的是合并ab树,每一步递归要做的事当前节点的值为a树和b树相加,左子树为a树左子树和b树左子树递归合并,右子树为a树右子树和b树右子树递归合并。
时间复杂度On
空间复杂度On
代码
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {res:=&TreeNode{}if root1==nil&&root2==nil{return nil}if root1!=nil&&root2!=nil{res.Val=root1.Val+root2.Valres.Left=mergeTrees(root1.Left,root2.Left)res.Right=mergeTrees(root1.Right,root2.Right)}else if root1!=nil{res.Val=root1.Valres.Left=mergeTrees(root1.Left,nil)res.Right=mergeTrees(root1.Right,nil)}else if root2!=nil{res.Val=root2.Valres.Right=mergeTrees(nil,root2.Right)res.Left=mergeTrees(nil,root2.Left)}return res
}
700.二叉搜索树中的搜索
思路
二叉搜索树中序遍历迭代即可
时间复杂度On
代码
func searchBST(root *TreeNode, val int) *TreeNode {stack:=[]*TreeNode{}cur:=rootfor cur!=nil||len(stack)>0{for cur!=nil{stack=append(stack,cur)cur=cur.Left}cur=stack[len(stack)-1]if cur.Val==val{return cur}stack=stack[:len(stack)-1]cur=cur.Right}return nil
}
98.验证二叉搜索树
思路
递归,每一层递归的目的是判断当前节点的左右子树的所有节点是否都小于或大于当前节点,然后再递归地判断左右子树是否是二叉搜索树。
时间复杂度Onlogn
还可以优化
官方题解
要知道中序遍历下,输出的二叉搜索树节点的数值是有序序列。
有了这个特性,验证二叉搜索树,就相当于变成了判断一个序列是不是递增的了。
时间复杂度On
代码
func isValidBST(root *TreeNode) bool {if root==nil{return true}if root.Left!=nil{ml,_:=maxmin(root.Left)if ml>=root.Val{return false}}if root.Right!=nil{_,mr:=maxmin(root.Right)if mr<=root.Val{return false}}return isValidBST(root.Left)&&isValidBST(root.Right)
}func maxmin(root *TreeNode) (int,int){max,min:=root.Val,root.Valif root.Left!=nil{maxl,minl:=maxmin(root.Left)if max<maxl{max=maxl}if min>minl{min=minl}}if root.Right!=nil{maxr,minr:=maxmin(root.Right)if max<maxr{max=maxr}if min>minr{min=minr}}return max,min
}
困难
开始递归的条件和者终止条件要保持一致性,比如默认只有节点不为空才开始递归,那么终止条件就可以不写节点为空。
今日收获
根据数组构建二叉树的统一写法。
res:=&TreeNode{}
res.Val=…
res.Left=递归…
验证二叉搜索树的写法。
相关文章:
二叉树part6 | ● 654.最大二叉树 ● 617.合并二叉树 ● 700.二叉搜索树中的搜索 ● 98.验证二叉搜索树
文章目录 654.最大二叉树思路代码 617.合并二叉树思路代码 700.二叉搜索树中的搜索思路代码 98.验证二叉搜索树思路官方题解代码困难 今日收获 654.最大二叉树 思路 前序遍历构造二叉树。 找出数组中最大值,然后递归处理左右子数组。 时间复杂度On2 空间复杂度On …...
Linux命令记录
Shells 查看当前系统shell cat /etc/shells # 输出 # /etc/shells: valid login shells /bin/sh /bin/bash /usr/bin/bash /bin/rbash /usr/bin/rbash /bin/dash /usr/bin/dash查看正在使用的shell echo $SHELL # 输出 /bin/bashLinux文件结构 bin:系统可执行文件b…...
eBPF 入门实践教程十五:使用 USDT 捕获用户态 Java GC 事件耗时
eBPF (扩展的伯克利数据包过滤器) 是一项强大的网络和性能分析工具,被广泛应用在 Linux 内核上。eBPF 使得开发者能够动态地加载、更新和运行用户定义的代码,而无需重启内核或更改内核源代码。这个特性使得 eBPF 能够提供极高的灵活性和性能,…...
Linux :: vim 编辑器的初次体验:三种 vim 常用模式 及 使用:打开编辑、退出保存关闭vim
前言:本篇是 Linux 基本操作篇章的内容! 笔者使用的环境是基于腾讯云服务器:CentOS 7.6 64bit。 学习集: C 入门到入土!!!学习合集Linux 从命令到网络再到内核!学习合集 目录索引&am…...
Linux内核进程创建流程
本文代码基于Linux5.10 内容主要参考《Linux内核深度解析》余华兵 当Linux内核要创建一个新进程时, 流程大致如下 ret fork(); if (ret 0) {/* 子进程装载程序 */ret execve(filename, argv, envp); } else if (ret > 0) {/* 父进程 */ } 大致可以分为创建新…...
【03.04】大数据教程--HTTP协议和静态Web服务器
HTTP协议和静态Web服务器 HTTP(Hypertext Transfer Protocol)是一种用于传输超文本的协议,它是Web上的基础通信协议。静态Web服务器是指能够提供静态内容(如HTML、CSS、JavaScript和图像文件)的服务器。 在本教程中&am…...
数据共享传输:台式机和笔记本同步文件!
为什么要在台式机和笔记本同步文件? “我想在台式机和笔记本同步文件。因为我工作时使用笔记本,在家里使用安装了Windows 10系统的台式机,我想要在笔记本和台式机之间同步应用程序、游戏、文档等。有没有一种可以在台式机和笔记本同步文件的…...
java设计模式(十二)代理模式
目录 定义模式结构角色职责代码实现静态代理动态代理jdk动态代理cglib代理 适用场景优缺点 定义 代理模式给某一个对象提供一个代理对象,并由代理对象控制对原对象的引用。说简单点,代理模式就是设置一个中间代理来控制访问原目标对象,以达到…...
Umi微前端水印踩坑以及解决方案
最近公司需要在管理后台加一个水印方案~ 项目用的umi方案,以为就是改一个配置的问题,后来发现坑点还蛮多~ 希望此稳定能帮助到用umi 的你们. 一. 先来说说心路历程 坑点1 umi的水印适配只能在layout中进行配置,也就是路由配置中layout为false的页面无法配置水印,比如说登录页…...
Android RK3588-12 hdmi-in Camera方式支持NV24格式
hdmi-in Camera方式支持NV24格式 modified: hardware/interfaces/camera/device/3.4/default/ExternalCameraDevice.cpp modified: hardware/interfaces/camera/device/3.4/default/ExternalCameraDeviceSession.cpp diff --git a/hardware/interfaces/camera/device/3.4…...
Hive窗口函数详细介绍
文章目录 Hive窗口函数概述样本数据表结构表数据 窗口函数窗口聚合函数count()SQL演示 sum()SQL演示 avg()SQL演示 min()SQL演示 max()SQL演示 窗口分析函数first_value() 取开窗第一个值应用场景SQL演示 last_value()取开窗最后一个值应用场景SQL演示 lag(col, n, default_val…...
牛客网【c语言练习】
单选题 下面代码段的输出是(-12 ) int main() {int a3; printf("%d\n",(aa-a*a)); } aa-9,此时还是等于3,因为a*a只是运算,并没有赋值;之后再算a-9,运算之前a等于3,运算…...
C++类和对象(上)
文章目录 🦍1. 面向过程和面向对象🦧2. 类的引入🐶3. 类的定义🦮4. 类的访问控制和封装🍖4.1 访问限定符🍖4.2 封装 🐩5. 类的作用域🐅6. 类的实例化🐄7. 类的大小计算&a…...
JavaScript 数据透视表 DHTMLX Pivot Crack
DHTMLX Pivot JavaScript 数据透视表 - 强大的数据汇总和报告 使用我们的高速 JavaScript/HTML5 Pivot 组件可视化您的复杂数据,从而提高您的商业智能。 它可以帮助您以方便的方式汇总大型数据集。 主要特征 纯 JavaScript 库,可轻松与任何服务器端集成…...
QT链接库设置
以windows 平台为例,在.pro 文件中: 1 增加 INCLUDEPATH <头文件路径> DEPENDPATH <头文件路径> 2 LIBS -L<库目录路径> -l<库得名字> 3 设置MT、MTD、MD、MDD运行时库 win32:CONFIG(debug, debug|release): { QMAKE_CFLAGS_…...
零点起飞学Android——期末考试课本复习重点
目录 第一章 认识Android第二章 Android常见界面布局第三章 Android常用基本控件第四章 Android 高级控件第五章 Android菜单和对话框 第一章 认识Android 1. Android 界面设计被称为______。 答案:布局 2. Android中常见的布局包括______、______ 、______ 、____…...
Redis为什么快?
目录 Redis为什么快?渐进式ReHash全局哈希表渐进式ReHash 缓存时间戳 Redis为什么快? 纯内存访问; 单线程避免上下文切换; 渐进式ReHash、缓存时间戳; 前面两个都比较好理解,下面我们主要来说下 渐进式…...
Zabbix从入门到精通以及案例实操系列
1、Zabbix入门 1.1、Zabbix概述 Zabbix是一款能够监控各种网络参数以及服务器健康性和完整性的软件。Zabbix使用灵活的通知机制,允许用户为几乎任何事件配置基于邮件的告警。这样可以快速反馈服务器的问题。基于已存储的数据,Zabbix提供了出色的报告和…...
水声声波频率如何划分?水声功率放大器可将频率放大到20MHz吗?
水声声波频率如何划分?水声功率放大器可将频率放大到20MHz吗? 现如今我们可以在地球任意地区实现通信,是因为电磁波的作用。但是我们都知道海洋占了全球十分之七面积,电磁波在水下衰减速度太快,无法做到远距离传输&am…...
网络攻防技术--论文阅读--《基于自动数据分割和注意力LSTM-CNN的准周期时间序列异常检测》
英文题目:Anomaly Detection in Quasi-Periodic Time Series based on Automatic Data Segmentation and Attentional LSTM-CNN 论文地址:Anomaly Detection in Quasi-Periodic Time Series Based on Automatic Data Segmentation and Attentional LST…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
Pinocchio 库详解及其在足式机器人上的应用
Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库,专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性,并提供了一个通用的框架&…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
Selenium常用函数介绍
目录 一,元素定位 1.1 cssSeector 1.2 xpath 二,操作测试对象 三,窗口 3.1 案例 3.2 窗口切换 3.3 窗口大小 3.4 屏幕截图 3.5 关闭窗口 四,弹窗 五,等待 六,导航 七,文件上传 …...
【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案
目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后,迭代器会失效,因为顺序迭代器在内存中是连续存储的,元素删除后,后续元素会前移。 但一些场景中,我们又需要在执行删除操作…...
Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案
在大数据时代,海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构,在处理大规模数据抓取任务时展现出强大的能力。然而,随着业务规模的不断扩大和数据抓取需求的日益复杂,传统…...
