代码随想录【Day20】| 654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树
654. 最大二叉树
题目链接
题目描述:
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下:
二叉树的根是数组中的最大元素。
左子树是通过数组中最大值左边部分构造出的最大二叉树。
右子树是通过数组中最大值右边部分构造出的最大二叉树。
通过给定的数组构建最大二叉树,并且输出这个树的根节点。
示例 :

提示:
给定的数组的大小在 [1, 1000] 之间。
nums 中的所有整数 互不相同
难点:
- 不能排序,排序会丢失左右位置信息
- 构造树采用递归前序遍历,如何保留父节点信息,保证构造链不断
思路:
时间复杂度:O()
空间复杂度:O()
class Solution {public TreeNode constructMaximumBinaryTree(int[] nums) {TreeNode root = constructNode(nums, 0, nums.length);return root;}private TreeNode constructNode(int[] nums, int left, int right) {if (left >= right) {return null;}if (right - left == 1) {return new TreeNode(nums[left]);}int maxValue = 0;int maxIdx = 0;for (int i = left; i < right; i++) {if (nums[i] > maxValue) {maxIdx = i;maxValue = nums[i];}}TreeNode root = new TreeNode(maxValue);root.left = constructNode(nums, left, maxIdx);root.right = constructNode(nums, maxIdx+1, right);return root;}
}
时长:
40min
收获:
构造返回类型为TreeNode的递归函数
617. 合并二叉树
题目链接
题目描述:
给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。
你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。
示例 1:

注意: 合并必须从两个树的根节点开始。
难点:
思路:
时间复杂度:O()
空间复杂度:O()
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {root1 = merge(root1, root2);return root1;}//1. 结点1结点2均为空结点//2. 结点1为空,结点2不空 ===> 将结点2赋给结点1//3. 结点1不空,结点2为空 ===> 将结点1返回//4. 结点1结点2均不空 ===> 结点1的值加上结点2的值,递归处理结点1、2左右结点//5. 返回结点1private TreeNode merge(TreeNode root1, TreeNode root2) {if (root1 == null && root2 == null) return null;if (root1 == null && root2 != null) {root1 = root2;}else if (root1 != null && root2 != null) {root1.val += root2.val;root1.left = merge(root1.left, root2.left);root1.right = merge(root1.right, root2.right);}return root1;}
}//简化整理一下
class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null) return root2;if (root2 == null) return root1;root1.val += root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}
}
时长:
20min
收获:
注意递归返回值
700. 二叉搜索树中的搜索
题目链接
题目描述:
给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。
例如,

在上述示例中,如果要找的值是 5,但因为没有节点值为 5,我们应该返回 NULL。
难点:
思路:
时间复杂度:O()
空间复杂度:O()
class Solution {public TreeNode searchBST(TreeNode root, int val) {if (root == null) return null;if (root.val == val) return root;if (root.val > val) {return searchBST(root.left, val);}return searchBST(root.right, val);}
}
时长:
5min
收获:
BST的性质
98. 验证二叉搜索树
题目链接
题目描述:
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。

难点:
不能单纯的比较左节点小于中间节点,右节点大于中间节点
思路:
要记录父节点
时间复杂度:O()
空间复杂度:O()
class Solution {TreeNode maxNode;public boolean isValidBST(TreeNode root) {if (root == null) return true;//左boolean left = isValidBST(root.left);if (!left) {return false;}//中if (maxNode != null && root.val <= maxNode.val) {return false; //中序遍历,maxNode代表当前遍历到的部分的最大值结点,如果遍历右子树,将会更新它}maxNode = root;//右boolean right = isValidBST(root.right);return right;}
}
时长:
12min
收获:
BST的性质,左右节点严格小于大于
本题很巧妙,先从左子树最下面开始判断,逐层返回左子树的根节点和当前树的根节点做判断
相关文章:
代码随想录【Day20】| 654. 最大二叉树、617. 合并二叉树、700. 二叉搜索树中的搜索、98. 验证二叉搜索树
654. 最大二叉树 题目链接 题目描述: 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下: 二叉树的根是数组中的最大元素。 左子树是通过数组中最大值左边部分构造出的最大二叉树。 右子树是通过数组中最大值右边部分构造出的最…...
C++空指针和野指针
空指针:指针被赋值为空 例如: int* p nullptr;int* p NULL; 空指针指向的地址是00000000,但空指针不可以解引用 野指针:指针指向了不可控的位置 例如: 未初始化 int* p; //野指针 越界访问 int intArr[5]{0, 1, …...
LinkedList正确的遍历方式-附源码分析
1.引子 记得之前面试过一个同学,有这么一个题目: LinkedList<String> list new LinkedList<>();for (int i 0; i < 1000; i) {list.add(i "");}请根据上面的代码,请选择比较恰当的方式遍历这个集合,并…...
【蓦然回首忆Java·基础卷Ⅱ】
文章目录对象内存解析方法的参数传递机制关键字:package、importpackage(包)JDK中主要的包介绍import(导入)JavaBeanUML类图继承的一些细节封装性中的4种权限修饰关键字:supersuper的理解super的使用场景子类中调用父类被重写的方法子类中调用父类中同名…...
Mybatis源码分析系列之第二篇:Mybatis的数据存储对象
前言:SQLSession是对JDBC的封装 一:SQLSession和JDBC的对照说明 左边是我们的客户端程序,右边是我们的MySQL数据仓,或者叫MySQL实例 Mybatis是对JDBC的封装,将JDBC封装成了一个核心的SQLSession对象 JDBC当中的核心对…...
防护设备检测实验室建设完整方案SICOLAB
防护设备检测实验室建造布局方案SICOLAB一、防护设备检测实验室通常需要划分为几个功能区域,包括:1、样品准备区:用于样品的接收、处理、准备等工作,通常包括样品接收台、洗手池、样品切割机等设备。2、实验操作区:用于…...
Linux知识之主机状态
1、查看系统资源占用 •可以通过top命令查看CPU、内存使用情况,类似Windows的任务管理器默认每5秒刷新一次,语法:直接输入top即可,按q或ctrl c退出 2、 top命令内容详解 •第一行:top:命令名称࿰…...
是时候为您的银行机构选择构建一个知识库了!
知识管理和自助服务客户支持在银行业至关重要。选择正确的知识库对于帮助客户和在内部共享信息同样重要。繁重的法规和合规性需求意味着银行必须在他们选择的知识库类型上投入大量思考。许多银行知识库已经过时,无法为客户提供成功使用您的产品和服务所需的信息。在…...
「TCG 规范解读」第7章 TPM工作组 TPM 总结
可信计算组织(Ttrusted Computing Group,TCG)是一个非盈利的工业标准组织,它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立,并采纳了由可信计算平台联盟(the Trusted Computing Platform Alli…...
一、Plugin Constructing the Boilerplate
构建样板文件 在本章中,你将学习如何为一个新插件构建最少的代码。从起点开始,您将看到如何获取GStreamer模板源代码。然后,您将学习如何使用一些基本工具来复制和修改模板插件,以创建一个新的插件。如果您遵循这里的示例&#x…...
15、存储过程与函数
文章目录1 存储过程概述1.1 理解1.2 分类2 创建存储过程2.1 语法分析2.2 代码举例3 调用存储过程3.1 调用格式3.2 代码举例3.3 如何调试4 存储函数的使用4.1 语法分析4.2 调用存储函数4.3 代码举例4.4 对比存储函数和存储过程5 存储过程和函数的查看、修改、删除5.1 查看5.2 修…...
uniapp 原生安卓开发插件(module),以及android环境本地调试(二)
uniapp 原生安卓开发插件(module),以及android环境本地调试(一) 1、前景 承接上一篇文章,由于uniapp每天只有限定的打包次数,所以每次插件调试都打包成为基座,这个不太方便&#x…...
【Java期末复习】《面向对象程序设计》练习库
目录 一、单选题 二、填空题 三、程序填空题 1、 super使用--有如下父类和子类的定义,根据要求填写代码 2、简单加法计算器的实现 3、House类 4、矩形类 5、创建一个Box类,求其体积 四、函数题 6-1 求圆面积自定义异常类 6-2 判断一个数列是…...
照片文件损坏能修复吗?
很多时候,我们都是把相机拍的照片保存在电脑上,或手机照片太多,也会上传到电脑里保存。这样就能腾出更多的存储空间。但在电脑里的照片文件有时会莫名其妙的损坏,提示已损坏等情况,一旦发生这样的事,这些照…...
Git分布式版本控制工具
1:目标了解Git基本概念 能够概述git工作流程 能够使用Git常用命令 熟悉Git代码托管服务 能够使用idea操作git 2:概述2.1:开发中的实际场景场景一:备份 小明负责的模块就要完成了,就在即将Release之前的一瞬间ÿ…...
Python爬虫(8)selenium爬虫后数据,存入sqlit3实现增删改查
之前的文章有关于更多操作方式详细解答,本篇基于前面的知识点进行操作,如果不了解可以先看之前的文章 Python爬虫(8)selenium爬虫后数据,存入sqlit3实现增删改查导入默认包和环境元素定位创建一个sqlit3表将爬虫到的信…...
最全Linux驱动开发全流程详细解析(持续更新)
Linux驱动开发详细解析 一、驱动概念 驱动与底层硬件直接打交道,充当了硬件与应用软件中间的桥梁。 具体任务 读写设备寄存器(实现控制的方式)完成设备的轮询、中断处理、DMA通信(CPU与外设通信的方式)进行物理内存…...
华为OD机试 - 乱序整数序列两数之和绝对值最小 | 机试题算法思路 【2023】
最近更新的博客 华为OD机试 - 简易压缩算法(Python) | 机试题算法思路 【2023】 华为OD机试题 - 获取最大软件版本号(JavaScript) 华为OD机试 - 猜字谜(Python) | 机试题+算法思路 【2023】 华为OD机试 - 删除指定目录(Python) | 机试题算法思路 【2023】 华为OD机试 …...
网上插画教学哪家质量好,汇总5大插画培训班
网上插画教学哪家质量好?给大家梳理了国内5家专业的插画师培训班,最新五大插画班排行榜,各有优势和特色! 一:国内知名插画培训机构排名 1、轻微课(五颗星) 主打课程有日系插画、游戏原画、古风插…...
对云原生集群网络流量可观测性的一点思考
问题背景 在云原生技术的广泛普及和实施过程中,笔者接触到的很多用户需求里都涉及到对云原生集群的可观测性要求。 实现集群的可观测性,是进行集群安全防护的前提条件 。而在可观测性的需求中,集群中容器和容器之间网络流量的可观测性需求是…...
web vue 项目 Docker化部署
Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段: 构建阶段(Build Stage):…...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频
使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
Matlab | matlab常用命令总结
常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
