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

【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 &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左子树 只包含 小于 当前节点的数。 节点的右子树只包含 大于 当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 英文题目 Given the root…...

[Qt] Qt Creator 编译输出乱码,问题页中的报错、警告内容,编译输出乱码

确保文件编码为"UTF-8"&#xff0c;"如果编码是UTF-8则添加"&#xff0c;如下图&#xff1a; 设置IDE环境语言跟随系统语言&#xff0c;Text codec for tools&#xff1a; "System" 瑞斯拜...

sed

1、sed的定义 sed是一种流编辑器&#xff0c;按行处理&#xff0c;一次处理一行内容 处理方式&#xff1a;如果只是展示&#xff0c;会放在缓冲区&#xff08;模式空间&#xff09;&#xff0c;展示结束后&#xff0c;会从模式空间把操作结果删除 一行一行处理&#xff0c;处…...

C++一文讲透thread中的detach和join的差别

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、thread详解二、线程何时运行三、线程启动方式1.join2.detach 总结 前言 无论哪种语言线程在绝大多数项目中都是会用到的&#xff0c;C也一样&#xff0c;C…...

当Windows台式电脑或笔记本电脑随机关机时,请先从这8个方面检查

序言 你的Windows笔记本电脑或PC是否意外关闭?笔记本电脑电池故障、电源线松动、过热、电源设置错误、驱动程序过时或电脑组件故障等问题都可能是罪魁祸首。如果你对这个问题感到沮丧,试试这些解决方案。 进行一些初步检查 与从电池中获取电力的笔记本电脑不同,台式电脑依…...

【凤凰房产-注册安全分析报告-缺少轨迹的滑动条】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…...

【建议收藏】逻辑回归面试题,机器学习干货、重点。

. . . . . . . . . . .纯 干 货 . . . . . . . . . . . .今天是机器学习面试题&#xff0c;16大块的内容&#xff0c;124个问题总结的第二期&#xff1a;逻辑回归面试题。 逻辑回归是一种用于解决分类问题的统计学习方法&#xff0c;尤其在二分类…...

C++使用教程

目录 一、软件使用 二、C基础规则补充 关键字 整型取值范围 浮点型取值范围 字符型使用规则 字符串型使用规则 布尔类型 常用的转义移字符 三、数组、函数、指针、结构体补充 1.数组 2.函数 声明&#xff1a; 分文件编写&#xff1a; 值传递&#xff1a; 3.指…...

k8s volcano + deepspeed多机训练 + RDMA ROCE+ 用户权限安全方案【建议收藏】

前提&#xff1a;nvidia、cuda、nvidia-fabricmanager等相关的组件已经在宿主机正确安装&#xff0c;如果没有安装可以参考我之前发的文章GPU A800 A100系列NVIDIA环境和PyTorch2.0基础环境配置【建议收藏】_a800多卡运行环境配置-CSDN博客文章浏览阅读1.1k次&#xff0c;点赞8…...

设计模式(七)创建者模式之建造者模式

这里写目录标题 概述需求需求类图BikeBuilderMobikeBuilderOfoBuilderDirectorClientClient优缺点使用场景 模式扩展ComputerClient创建者模式对比工厂方法模式VS建造者模式抽象工厂模式VS建造者模式 总结 概述 建造者模式又叫生成器模式&#xff0c;是一种对象构建模式。它可…...

# class中的__call__方法解析

class中的__call__方法解析 文章目录 class中的__call__方法解析1. 为什么要有call&#xff0c;什么情况下用call&#xff1f;1.1 为什么要有 __call__ 方法1.2 没有 __call__ 方法是否可以1.3 使用 __call__ 方法的典型场景1.3.1 示例1&#xff1a;简单函数对象1.3.2 示例2&am…...

React逻辑复用的方式都有哪些

在日常开发中&#xff0c;能够优雅的复用组件和逻辑&#xff0c;是优秀开发者的职责。在react中&#xff0c;复用逻辑的方式有很多&#xff0c;可以适用于不同的业务场景。今天说三个比较有代表性的&#xff0c;Render Props、HOC、Hooks Render Props 创建一个接受函数作为其…...

【LinuxC语言】线程重入

文章目录 前言线程重入是什么线程重入实现示例代码总结前言 在并发编程中,我们经常需要处理多个线程同时访问和修改共享资源的问题。这可能会导致数据竞争和状态不一致,从而使程序的行为变得不可预测。为了解决这个问题,我们引入了一种称为“线程重入”的机制。线程重入,或…...

【Streamlit学习笔记】Streamlit-ECharts箱型图添加均值和最值label

Streamlit-ECharts Streamlit-ECharts是一个Streamlit组件&#xff0c;用于在Python应用程序中展示ECharts图表。ECharts是一个由百度开发的JavaScript数据可视化库Apache ECharts 安装模块库 pip install streamlitpip install streamlit-echarts绘制箱型图展示 在基础箱型…...

Docker镜像仓库:存储与分发Docker镜像的中央仓库

探索Docker镜像仓库&#xff1a;存储与分发Docker镜像的中央仓库 如果你是Docker的新手&#xff0c;或者已经在使用Docker但还不太了解Docker镜像仓库&#xff0c;那么这篇博客将是你的最佳指南。我们将从基础概念开始&#xff0c;逐步深入&#xff0c;帮助你全面掌握Docker注…...

FreeRTOS必考面试题及参考答案

什么是RTOS?FreeRTOS是什么?它主要应用于哪些领域? RTOS,即实时操作系统(Real-Time Operating System),是一种专门为实时应用程序设计的操作系统,它强调的是对外部事件的快速响应和可预测性。实时系统通常要求在严格的时限内完成关键任务,因此RTOS具备优先级调度、确…...

面试题2:从浏览器输入一个URL,到最终展示前端页面这一过程,会发生什么?

这是一个高频的面试题目。 题目答案是开放性的&#xff0c;一般以后端开发的角度回答。 当地址栏输入一个 URL 后&#xff1a; 一、首先会进行 DNS 域名解析 DNS 域名解析&#xff1a;网络上的设备都是通过 IP 地址&#xff0c;作为身份标识的。但是由于点分十进制的 IP 地址 …...

<Rust><iced><resvg>基于rust使用iced构建GUI实例:使用resvg库实现svg转png

前言 本文是使用rust库resvg来将svg图片转为png图片。 环境配置 系统&#xff1a;windows 平台&#xff1a;visual studio code 语言&#xff1a;rust 库&#xff1a;resvg 代码分析 resvg是一个基于rust的svg渲染库&#xff0c;其官方地址&#xff1a; An SVG rendering li…...

面试突击:Java 中的泛型

本文已收录于&#xff1a;https://github.com/danmuking/all-in-one&#xff08;持续更新&#xff09; 前言 哈喽&#xff0c;大家好&#xff0c;我是 DanMu。今天想和大家聊聊 Java 中的泛型。 什么是泛型&#xff1f; Java 泛型&#xff08;Generics&#xff09; 是 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 简介 组合框其实就是把一个编辑框和一…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

简易版抽奖活动的设计技术方案

1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)

引言 在人工智能飞速发展的今天&#xff0c;大语言模型&#xff08;Large Language Models, LLMs&#xff09;已成为技术领域的焦点。从智能写作到代码生成&#xff0c;LLM 的应用场景不断扩展&#xff0c;深刻改变了我们的工作和生活方式。然而&#xff0c;理解这些模型的内部…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...