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

代码随想录算法训练营day22 | 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

654.最大二叉树

和构造二叉树差不多,本题使用索引的方式

class Solution:def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:return self.traversal(nums, 0, len(nums)-1)def traversal(self, nums, left, right):if left > right:returnmax_value_index = leftfor index in range(left+1, right+1):if nums[index] > nums[max_value_index]:max_value_index = indexroot = TreeNode(nums[max_value_index])root.left = self.traversal(nums, left, max_value_index-1)root.right = self.traversal(nums, max_value_index+1, right)return root      

617.合并二叉树

最后合成的树放在root1上

class Solution:def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:if not root1:return root2if not root2:return root1root1.val = root1.val + root2.valroot1.left = self.mergeTrees(root1.left, root2.left)root1.right = self.mergeTrees(root1.right, root2.right)return root1

700.二叉搜索树中的搜索

搜索二叉树左子树的值都比根节点小,右子树的值都是根节点大,利用这个特性将大大提高搜索效率

递归法

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:if not root:returnif root.val == val:return rootif root.val > val:return self.searchBST(root.left, val)if root.val < val:return self.searchBST(root.right, val)

迭代法

class Solution:def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:while root:if root.val == val:return rootelif root.val > val:root = root.leftelse:root = root.rightreturn

98.验证二叉搜索树

此题不能单纯比较根节点大于左节点小于右节点,因为二叉搜索树需要左子树所有的节点都小于根节点,右子树所有的节点都大于根节点

本题使用中序遍历,如果是二叉搜索树的话,可以得到递增序列。因此在中序遍历中比较当前值是否大于前一个值,如果不满足,则返回False

class Solution:def __init__(self):self.pre = Nonedef isValidBST(self, root: Optional[TreeNode]) -> bool:if not root:return Trueleft = self.isValidBST(root.left)if self.pre is not None and root.val <= self.pre:return Falseself.pre = root.valright = self.isValidBST(root.right)return left and right

注意:本题中if self.pre is not None 不能替换为if self.pre,因为pre为0的时候,if self.pre 是False

相关文章:

代码随想录算法训练营day22 | 654.最大二叉树、617.合并二叉树、700.二叉搜索树中的搜索、98.验证二叉搜索树

654.最大二叉树 和构造二叉树差不多&#xff0c;本题使用索引的方式 class Solution:def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:return self.traversal(nums, 0, len(nums)-1)def traversal(self, nums, left, right):if left > r…...

企业信息防泄漏软件分析:盘点常用企业信息防泄漏软件

在当今数字化时代&#xff0c;企业信息防泄漏软件已成为保障企业数据安全不可或缺的一环。市面上众多的防泄漏软件各具特色&#xff0c;如何从中挑选出最适合自己企业的产品&#xff0c;成为了一个值得深入探讨的话题。 一、企业信息防泄漏软件分析 首先&#xff0c;我们需要…...

Rancher-Kubewarden-保姆级教学-含Demo测试

一、什么是Kubewarden&#xff1f; What is Kubewarden? | Kubewarden 1、就是容器集群的准入策略引擎。 1、使用的策略其实就是k8s原生的security context. 2、使用WebAssembly来编写策略。 1、WebAssembly&#xff0c;可以使用擅长的开发语言来编写策略。&#xff08;下面的…...

Lumerical Script ------ array 数组类型 和 matrix 矩阵类型

Lumerical Script ------ array 数组类型 和 matrix 矩阵类型 引言正文array 数组类型matrix 矩阵类型引言 这篇仅仅用作个人笔记,因为作者本人比较擅长 Python,每次写 Lumerical Script 总是会写错代码。 正文 array 数组类型 Lumerical Script 脚本有些像 Matlab 脚本,…...

Springboot自动装配源码分析

版本 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.3.4.RELEASE</version><relativePath/> <!-- lookup parent from repository --> </par…...

Visual Transformer (ViT)模型详解 动图讲解

1 Vit简介 1.1 Vit的由来 ViT是2020年Google团队提出的将Transformer应用在图像分类的模型,虽然不是第一篇将transformer应用在视觉任务的论文,但是因为其模型“简单”且效果好,可扩展性强(scalable,模型越大效果越好),成为了transformer在CV领域应用的里程碑著作,也…...

C++:完美转发(一)(std::forward)

一、理解引用折叠 &#xff08;一&#xff09;引用折叠 1. 在C中&#xff0c;“引用的引用”是非法的。像 auto& &rx x;&#xff08;注意两个&之间有空格&#xff09;这种直接定义引用的引用是不合法的&#xff0c;但是编译器在通过类型别名或模板参数推导等语境…...

西部首个全域直播基地,打造西部直播基地领军形象

天府锋巢直播产业基地作为西部直播产业的领军者&#xff0c;以其前瞻性的战略布局和卓越的服务体系&#xff0c;正加速推动全域直播的快速发展&#xff0c;助力直播产业实现新升级。该基地作为成都规模最大的直播基地&#xff0c;以加快全域直播为核心目标&#xff0c;通过促进…...

钟表——蓝桥杯十三届2022国赛大学B组真题

问题分析 这个问题的关键有两点&#xff1a;1.怎么计算时针&#xff0c;分针&#xff0c;秒针之间的夹角&#xff0c;2.时针&#xff0c;分针&#xff0c;秒针都是匀速运动的&#xff0c;并非跳跃性的。问题1很好解决看下面的代码就能明白&#xff0c;我们先考虑问题2&#xf…...

CSS 之 圆形波浪进度条效果

一、简介 ​ 本篇博客讲述了如何实现一个圆形波浪进度条的样式效果&#xff0c;具体效果参考下方GIF图。该样式的加载进度条可以用在页面跳转或数据处理等情况下的加载动画&#xff0c;比起普通的横条进度条来说&#xff0c;样式效果更生动美观。 实现思路&#xff1a; ​ 这…...

按下鼠标进行拖拽,让元素跟随鼠标进行移动,鼠标抬起,元素停止移;js鼠标拖拽 (鼠标按下事件:onmousedown、鼠标移动事件:onmousemove、鼠标抬起事件:onmouseup)

需求如下&#xff1a; 按下鼠标进行拖拽&#xff0c;让元素跟随鼠标进行移动&#xff0c;鼠标抬起&#xff0c;元素停止移动。 解析&#xff1a; 鼠标按下事件&#xff1a;onmousedown 鼠标移动事件&#xff1a;onmousemove 鼠标抬起事件&#xff1a;onmouseup <!DOCT…...

第十二章 项目采购管理

12.1 规划采购管理 12.2 实施采购 12.3 控制采购 项目经理通常没有签订合同的权限&#xff0c;但必须熟悉正规的采购流程&#xff1b; 协议是采购的核心文件&#xff0c;关于协议我们要知道&#xff1a; 协议包括&#xff1a;合同、服务水平协议、谅解、协议备忘录或采购订单 ❗…...

PSFR-GAN复现

写在前面&#xff1a;本博客仅作记录学习之用&#xff0c;部分图片来自网络&#xff0c;如需引用请注明出处&#xff0c;同时如有侵犯您的权益&#xff0c;请联系删除&#xff01; 文章目录 前言快速开始安装依赖权重下载及复原 训练网络数据集训练脚本 代码详解训练BaseOptio…...

函数和数组

一、函数 1.函数使用方法 定义函数再引用函数 2.基本函数格式 基本格式1&#xff1a; function 函数名{ ​ 命令序列 } 基本格式2&#xff1a; 函数名&#xff08;&#xff09;{ 命令序列 } 基本格式3&#xff1a; function func_name &#xff08;&#xff09; {…...

docker安装时报错:Error: Nothing to do

安装docker时报以下错误 解决方法&#xff1a; 1.下载关于docker的相关依赖环境 yum -y install yum-utils device-mapper-persistent-data lvm22.设置下载Docker的镜像源 yum-config-manager --add-repo http://mirrors.aliyun.com/docker-ce/linux/centos/docker-ce.repo3…...

白盒测试:覆盖测试及测试用例设计

白盒测试&#xff1a;覆盖测试及测试用例设计 一、实验目的 1、掌握白盒测试的概念。 2、掌握逻辑覆盖法。 二、实验任务 某工资计算程序功能如下&#xff1a;若雇员月工作小时超过40小时&#xff0c;则超过部分按原小时工资的1.5倍的加班工资来计算。若雇员月工作小时超过…...

Java高级开发2024高频面试提问题目

1、请先简单自我介绍一下自己&#xff1f;&#xff08;一般不超过5min&#xff09; 2、你最熟悉的项目是哪一个&#xff0c;讲一下用了哪些技术栈&#xff1f;&#xff08;尽量讲出系统架构图使用到的技术组件和为什么选型这个组件&#xff1f;&#xff09; 3、你项目中使用什…...

Kamailio openssl 3.0.x 需要注意的事项

我们留意到 Debian Bookworm 安装的 openssl 版本是 3.0.x 这里有几个地方要注意&#xff1a; modparam("tls", "init_mode", 1)核心参数 tls_threads_mode 配置为 1 或者 配置为 2&#xff0c;默认为 0版本建议用 5.8.1&#xff0c;貌似 5.7.x 也行 参…...

SpringAMQP Work Queue 工作队列

消息模型: 代码模拟: 相较于之前的基础队列&#xff0c;该队列新增了消费者 不再是一个&#xff0c;所以我们通过代码模拟出两个consumer消费者。在原来的消费者类里写两个方法 其中消费者1效率高 消费者2效率低 RabbitListener(queues "simple.queue")public voi…...

一分钟带你了解什么是等保测评

等保测评&#xff0c;即网络安全等级保护测评&#xff0c;是依据国家信息安全等级保护制度规定&#xff0c;对信息系统进行安全技术测评和安全管理测评&#xff0c;以确定系统的安全保护水平是否达到预定的安全等级要求。以下是等保测评的相关知识点总结&#xff1a; 测评概述&…...

避开这些坑!海康威视嵌入式HR面常见‘送命题’与应答策略(附真实案例)

海康威视嵌入式HR面试避坑指南&#xff1a;6类高频"送命题"拆解与实战话术 在技术岗位的招聘流程中&#xff0c;HR面试往往是最容易被轻视却暗藏最多陷阱的环节。许多嵌入式开发者在技术面表现出色&#xff0c;却在看似轻松的HR面中意外折戟。通过对海康威视近三年嵌…...

从零构建CPWC超声成像仿真:Field II实战与模块化工作流解析

1. CPWC超声成像仿真入门指南 第一次接触CPWC超声成像仿真时&#xff0c;我被各种专业术语和复杂的数学公式搞得晕头转向。经过几个月的实战摸索&#xff0c;终于总结出一套小白也能快速上手的方法。CPWC&#xff08;相干平面波复合&#xff09;是近年来超声成像领域的热门技术…...

PCL2-CE社区版启动器:终极指南打造个性化Minecraft游戏中心

PCL2-CE社区版启动器&#xff1a;终极指南打造个性化Minecraft游戏中心 【免费下载链接】PCL-CE PCL2 社区版&#xff0c;可体验上游暂未合并的功能 项目地址: https://gitcode.com/gh_mirrors/pc/PCL-CE PCL2-CE社区版启动器是一款功能强大的开源Minecraft启动工具&…...

Python 性能优化避坑指南:回归风险防控、基准压测与安全回滚实战

Python 性能优化避坑指南&#xff1a;回归风险防控、基准压测与安全回滚实战 &#x1f4cc; 性能优化&#xff0c;为什么总让人又爱又怕&#xff1f; Python 从 1991 年 Guido van Rossum 创造至今&#xff0c;已成长为全球开发者首选“胶水语言”。其简洁优雅的语法、动态类…...

PyQt5实战:用QTreeView+QStandardItemModel快速构建你的第一个树形文件浏览器(附完整代码)

PyQt5实战&#xff1a;用QTreeViewQStandardItemModel快速构建你的第一个树形文件浏览器 每次看到电脑资源管理器左侧那整齐的目录树&#xff0c;你是否好奇过它是如何实现的&#xff1f;今天我们就用PyQt5的QTreeView和QStandardItemModel组件&#xff0c;从零开始打造一个简…...

[特殊字符] Local Moondream2图文对话教程:详细步骤实现自定义问题提问

Local Moondream2图文对话教程&#xff1a;详细步骤实现自定义问题提问 1. 引言&#xff1a;让电脑拥有"眼睛"的智能工具 你是否曾经希望电脑能像人一样看懂图片&#xff0c;并且回答关于图片内容的问题&#xff1f;Local Moondream2就是这样一款神奇的工具&#x…...

AI系统-21AI芯片之NoC总线

在大型SoC芯片&#xff0c;特别是AI SoC中&#xff0c;存在多个异构核子系统&#xff0c;非常的大和复杂。对应芯片设计中&#xff0c;一个重要的技术就是NoC&#xff0c;要想富先修路&#xff0c;NoC就是通信的路。而且SoC把很多硬件模块集成到一个芯片上就是为了让路好走&…...

python高校大学生家教平台的设计与开发

目录需求分析与功能规划技术栈选型数据库设计关键功能实现测试与部署持续迭代项目技术支持源码获取详细视频演示 &#xff1a;文章底部获取博主联系方式&#xff01;同行可合作需求分析与功能规划 明确平台核心需求&#xff0c;包括用户角色划分&#xff08;学生、教师、管理员…...

**发散创新:策略即代码 —— 用 Rust实现动态权限控制引擎**在现代软件架构中,**权限管理不再是静态配

发散创新&#xff1a;策略即代码 —— 用 Rust 实现动态权限控制引擎 在现代软件架构中&#xff0c;权限管理不再是静态配置的附属品&#xff0c;而是核心业务逻辑的一部分。传统 RBAC&#xff08;基于角色的访问控制&#xff09;虽然成熟&#xff0c;但在微服务、多租户和复杂…...

Android 性能优化:内存泄漏排查与解决

Android性能优化&#xff1a;内存泄漏排查与解决 在Android开发中&#xff0c;性能优化是提升用户体验的关键环节&#xff0c;而内存泄漏则是常见却容易被忽视的问题。内存泄漏会导致应用占用内存持续增加&#xff0c;最终引发卡顿、崩溃甚至被系统强制终止。如何高效排查与解…...