【LeetCode】Hot100:验证二叉搜索树
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下:
节点的左子树
只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
英文题目
Given the root of a binary tree, determine if it is a valid binary search tree (BST).
A valid BST is defined as follows:
The left subtreeof a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.
解题思路
画了一个四层的二叉树,发现递归方法是,左子树的最右节点应该比根节点小,右子树的最左节点应该比根节点大,基于此写的代码(事实上只要想着所有点,然后更新边界,就可以不用重复遍历来递归了)
AC代码
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:def isValidBST(self, root: Optional[TreeNode]) -> bool:def judge(root):if root.left is None and root.right is None:return Trueif root is None:return Trueleft, right, leftflag, rightflag = root.left, root.right, True, Trueif left is not None:while left.right is not None:left = left.rightleftflag = root.val > left.val and judge(root.left)if right is not None:while right.left is not None:right = right.leftrightflag = root.val < right.val and judge(root.right)return leftflag and rightflagreturn judge(root)
官方题解
想到使用边界后面思路就一下子通了
class Solution:def isValidBST(self, root: TreeNode) -> bool:stack, inorder = [], float('-inf')while stack or root:while root:stack.append(root)root = root.leftroot = stack.pop()# 如果中序遍历得到的节点的值小于等于前一个 inorder,说明不是二叉搜索树if root.val <= inorder:return Falseinorder = root.valroot = root.rightreturn True相关文章:
【LeetCode】Hot100:验证二叉搜索树
给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下: 节点的左子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 英文题目 Given the root…...
[Qt] Qt Creator 编译输出乱码,问题页中的报错、警告内容,编译输出乱码
确保文件编码为"UTF-8","如果编码是UTF-8则添加",如下图: 设置IDE环境语言跟随系统语言,Text codec for tools: "System" 瑞斯拜...
sed
1、sed的定义 sed是一种流编辑器,按行处理,一次处理一行内容 处理方式:如果只是展示,会放在缓冲区(模式空间),展示结束后,会从模式空间把操作结果删除 一行一行处理,处…...
C++一文讲透thread中的detach和join的差别
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、thread详解二、线程何时运行三、线程启动方式1.join2.detach 总结 前言 无论哪种语言线程在绝大多数项目中都是会用到的,C也一样,C…...
当Windows台式电脑或笔记本电脑随机关机时,请先从这8个方面检查
序言 你的Windows笔记本电脑或PC是否意外关闭?笔记本电脑电池故障、电源线松动、过热、电源设置错误、驱动程序过时或电脑组件故障等问题都可能是罪魁祸首。如果你对这个问题感到沮丧,试试这些解决方案。 进行一些初步检查 与从电池中获取电力的笔记本电脑不同,台式电脑依…...
【凤凰房产-注册安全分析报告-缺少轨迹的滑动条】
前言 由于网站注册入口容易被黑客攻击,存在如下安全问题: 1. 暴力破解密码,造成用户信息泄露 2. 短信盗刷的安全问题,影响业务及导致用户投诉 3. 带来经济损失,尤其是后付费客户,风险巨大,造…...
【建议收藏】逻辑回归面试题,机器学习干货、重点。
. . . . . . . . . . .纯 干 货 . . . . . . . . . . . .今天是机器学习面试题,16大块的内容,124个问题总结的第二期:逻辑回归面试题。 逻辑回归是一种用于解决分类问题的统计学习方法,尤其在二分类…...
C++使用教程
目录 一、软件使用 二、C基础规则补充 关键字 整型取值范围 浮点型取值范围 字符型使用规则 字符串型使用规则 布尔类型 常用的转义移字符 三、数组、函数、指针、结构体补充 1.数组 2.函数 声明: 分文件编写: 值传递: 3.指…...
k8s volcano + deepspeed多机训练 + RDMA ROCE+ 用户权限安全方案【建议收藏】
前提:nvidia、cuda、nvidia-fabricmanager等相关的组件已经在宿主机正确安装,如果没有安装可以参考我之前发的文章GPU A800 A100系列NVIDIA环境和PyTorch2.0基础环境配置【建议收藏】_a800多卡运行环境配置-CSDN博客文章浏览阅读1.1k次,点赞8…...
设计模式(七)创建者模式之建造者模式
这里写目录标题 概述需求需求类图BikeBuilderMobikeBuilderOfoBuilderDirectorClientClient优缺点使用场景 模式扩展ComputerClient创建者模式对比工厂方法模式VS建造者模式抽象工厂模式VS建造者模式 总结 概述 建造者模式又叫生成器模式,是一种对象构建模式。它可…...
# class中的__call__方法解析
class中的__call__方法解析 文章目录 class中的__call__方法解析1. 为什么要有call,什么情况下用call?1.1 为什么要有 __call__ 方法1.2 没有 __call__ 方法是否可以1.3 使用 __call__ 方法的典型场景1.3.1 示例1:简单函数对象1.3.2 示例2&am…...
React逻辑复用的方式都有哪些
在日常开发中,能够优雅的复用组件和逻辑,是优秀开发者的职责。在react中,复用逻辑的方式有很多,可以适用于不同的业务场景。今天说三个比较有代表性的,Render Props、HOC、Hooks Render Props 创建一个接受函数作为其…...
【LinuxC语言】线程重入
文章目录 前言线程重入是什么线程重入实现示例代码总结前言 在并发编程中,我们经常需要处理多个线程同时访问和修改共享资源的问题。这可能会导致数据竞争和状态不一致,从而使程序的行为变得不可预测。为了解决这个问题,我们引入了一种称为“线程重入”的机制。线程重入,或…...
【Streamlit学习笔记】Streamlit-ECharts箱型图添加均值和最值label
Streamlit-ECharts Streamlit-ECharts是一个Streamlit组件,用于在Python应用程序中展示ECharts图表。ECharts是一个由百度开发的JavaScript数据可视化库Apache ECharts 安装模块库 pip install streamlitpip install streamlit-echarts绘制箱型图展示 在基础箱型…...
Docker镜像仓库:存储与分发Docker镜像的中央仓库
探索Docker镜像仓库:存储与分发Docker镜像的中央仓库 如果你是Docker的新手,或者已经在使用Docker但还不太了解Docker镜像仓库,那么这篇博客将是你的最佳指南。我们将从基础概念开始,逐步深入,帮助你全面掌握Docker注…...
FreeRTOS必考面试题及参考答案
什么是RTOS?FreeRTOS是什么?它主要应用于哪些领域? RTOS,即实时操作系统(Real-Time Operating System),是一种专门为实时应用程序设计的操作系统,它强调的是对外部事件的快速响应和可预测性。实时系统通常要求在严格的时限内完成关键任务,因此RTOS具备优先级调度、确…...
面试题2:从浏览器输入一个URL,到最终展示前端页面这一过程,会发生什么?
这是一个高频的面试题目。 题目答案是开放性的,一般以后端开发的角度回答。 当地址栏输入一个 URL 后: 一、首先会进行 DNS 域名解析 DNS 域名解析:网络上的设备都是通过 IP 地址,作为身份标识的。但是由于点分十进制的 IP 地址 …...
<Rust><iced><resvg>基于rust使用iced构建GUI实例:使用resvg库实现svg转png
前言 本文是使用rust库resvg来将svg图片转为png图片。 环境配置 系统:windows 平台:visual studio code 语言:rust 库:resvg 代码分析 resvg是一个基于rust的svg渲染库,其官方地址: An SVG rendering li…...
面试突击:Java 中的泛型
本文已收录于:https://github.com/danmuking/all-in-one(持续更新) 前言 哈喽,大家好,我是 DanMu。今天想和大家聊聊 Java 中的泛型。 什么是泛型? Java 泛型(Generics) 是 JDK 5…...
3_2、MFC常用控件用法:组合框、滚动条和图片控件
MFC控件用法 1、组合框1.1 简介1.2 创建CComboBox类的主要成员函数 1.3 实例 2、滚动条控件2.1 简介2.2 创建CScrollBar类的主要成员函数 2.3 实例 3、图片控件3.1 简介3.2 创建图片控件静态加载图片图片控件动态加载图片 1、组合框 1.1 简介 组合框其实就是把一个编辑框和一…...
Java如何权衡是使用无序的数组还是有序的数组
在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
如何在网页里填写 PDF 表格?
有时候,你可能希望用户能在你的网站上填写 PDF 表单。然而,这件事并不简单,因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件,但原生并不支持编辑或填写它们。更糟的是,如果你想收集表单数据ÿ…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
Linux 中如何提取压缩文件 ?
Linux 是一种流行的开源操作系统,它提供了许多工具来管理、压缩和解压缩文件。压缩文件有助于节省存储空间,使数据传输更快。本指南将向您展示如何在 Linux 中提取不同类型的压缩文件。 1. Unpacking ZIP Files ZIP 文件是非常常见的,要在 …...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
