二叉树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…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...
ubuntu22.04有线网络无法连接,图标也没了
今天突然无法有线网络无法连接任何设备,并且图标都没了 错误案例 往上一顿搜索,试了很多博客都不行,比如 Ubuntu22.04右上角网络图标消失 最后解决的办法 下载网卡驱动,重新安装 操作步骤 查看自己网卡的型号 lspci | gre…...
