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

【LeetCode|数据结构】剑指 Offer 33. 二叉搜索树的后序遍历序列

题目链接

剑指 Offer 33. 二叉搜索树的后序遍历序列

标签

二叉搜索树、后序遍历

步骤

  1. 二叉搜索树的左子树的节点值 ≤ \le 根节点值 ≤ \le 右子树的节点值;
  2. 对于后序遍历序列最后一个元素的值为根节点的值;

由上面的两个性质可以得出,对于给定的后序序列 arr

Step1. 根据 arr 的最后一个元素,将其之前的序列进行划分(左子树、右子树);如果存在不能划分的情况,返回 false

int flag = arr[r];
int mark = -1; // first elem > flag
for (int i = l; i < r; i++) { // check from idx:l to r-1if (arr[i] > flag) {mark = i;break;}
}
if (mark != -1) {for (int i = mark; i < r; i++) {if (arr[i] < flag) {return false;}}
} else {mark = l + 1;
}

Step2. 递归判断左右子区间,直至当前区间不能再被划分。

bool judge(vector<int> &arr, int l, int r) {if (l >= r) {return true;}/*****balabala*****/return judge(arr, l, mark-1) && judge(arr, mark, r-1);
}

完整代码(C++)

class Solution {
public:bool judge(vector<int> &arr, int l, int r) {if (l >= r) {return true;}// l <= r// step1. partitionint flag = arr[r];int mark = -1; // first elem gt flagfor (int i = l; i < r; i++) { // check from idx:l to r-1if (arr[i] > flag) {mark = i;break;}}if (mark != -1) {for (int i = mark; i < r; i++) {if (arr[i] < flag) {return false;}}} else {mark = l + 1;}return judge(arr, l, mark-1) && judge(arr, mark, r-1);}bool verifyPostorder(vector<int>& postorder) {return judge(postorder, 0, postorder.size()-1);        }
};

相关文章:

【LeetCode|数据结构】剑指 Offer 33. 二叉搜索树的后序遍历序列

题目链接 剑指 Offer 33. 二叉搜索树的后序遍历序列 标签 二叉搜索树、后序遍历 步骤 二叉搜索树的左子树的节点值 ≤ \le ≤根节点值 ≤ \le ≤右子树的节点值&#xff1b;对于后序遍历序列最后一个元素的值为根节点的值&#xff1b; 由上面的两个性质可以得出&#xff…...

自定义协程

难点 自己写了一遍协程&#xff0c;困难的地方在于unity中的执行顺序突然发现unity里面可以 yield return 的其实有很多 WaitForSeconds WaitForSecondsRealtime WaitForEndOfFrame WaitForFixedUpdate WaitUntil WaitWhile IEnumerator&#xff08;可以用于协程嵌套&#xf…...

【Atcoder】 [ABC240Ex] Sequence of Substrings

题目链接 Atcoder方向 Luogu方向 题目解法 先考虑一个性质&#xff0c;选出的子串长度不会超过 2 n \sqrt {2n} 2n ​ 考虑最劣的选法是选出长度为 1 , 2 , 3 , . . . 1,2,3,... 1,2,3,... 的子串&#xff08;如果后一个选出的串比前一个子串长度大超过1&#xff0c;那么后…...

真机二阶段之堆叠技术

堆叠技术 --- 可以将多台真实的物理设备逻辑上抽象成一台 思科 -- VPC 华为 -- iStack和CSS 华三 -- IRF 锐捷 -- VSU iStack和CSS的区别&#xff1a; CSS --- 集群 --- 它仅支持将两台支持集群的交换机逻辑上整合成一台设备。 iStack --- 堆叠 --- 可以将多台支持堆叠的交换…...

简单、快速、无需注册的在线 MockJs 工具

简单、快速、无需注册的 MockJs 工具。通过参数来返回数据&#xff0c;传入什么参数就返回什么数据。 使用 接口只支持返回文本类数据&#xff0c;不支持图片、流数据等。 json 调用接口 https://mock.starxg.com/?responseBody{“say”:“hello”}&contentTypeapplic…...

【Linux取经路】探索进程状态之僵尸进程 | 孤儿进程

文章目录 一、进程状态概述1.1 运行状态详解1.2 阻塞状态详解1.3 挂起状态详解 二、具体的Linux操作系统中的进程状态2.1 Linux内核源代码2.2 查看进程状态2.3 D磁盘休眠状态(Disk sleep)2.4 T停止状态(stopped) 三、僵尸进程3.1 僵尸进程危害总结 四、孤儿进程五、结语 一、进…...

第十二章MyBatis动态SQL

if标签与where标签 if标签 test如果为true就会拼接查询条件&#xff0c;否则不会 当没有使用Param&#xff0c;test出现arg0/param1当使用Param&#xff0c;test为Param指定的值当使用Pojo&#xff0c;test为对象的属性名 select * from car where <if test"name!n…...

redis--发布订阅

redis的发布和订阅 在Redis中&#xff0c;发布-订阅&#xff08;Publish-Subscribe&#xff0c;简称Pub/Sub&#xff09;是一种消息传递模式&#xff0c;用于在不同的客户端之间传递消息&#xff0c;允许一个消息发布者将消息发送给多个订阅者。这种模式适用于解耦消息发送者和…...

链表2-两两交换链表中的节点删除链表的倒数第N个节点链表相交环形链表II

今天记录的题目&#xff1a; ● 24. 两两交换链表中的节点 ● 19.删除链表的倒数第N个节点 ● 面试题 02.07. 链表相交 ● 142.环形链表II 两两交换链表中的节点 题目链接&#xff1a;24. 两两交换链表中的节点 这题比较简单&#xff0c;记录好两个节点&#xff0c;交换其nex…...

数据结构之并查集

并查集 1. 并查集原理2. 并查集实现3. 并查集应用3.1 省份数量3.2 等式方程的可满足性 4. 并查集的优缺点及时间复杂度 1. 并查集原理 并查表原理是一种树型的数据结构&#xff0c;用于处理一些不相交集合的合并及查询问题。并查集的思想是用一个数组表示了整片森林&#xff0…...

[element-ui] el-date-picker a-range-picker type=“daterange“ rules 校验

项目场景&#xff1a; 在项目中表单提交有时间区间校验 问题描述 想当然的就和其他单个输入框字符串校验&#xff0c;导致提交保存的时候 &#xff0c;初次日期未选择&#xff0c;规则提示。后续在同一表单上继续提交时&#xff0c;校验失效。走进了死胡同&#xff0c;一直以…...

Dockers搭建个人网盘、私有仓库,Dockerfile制作Nginx、Lamp镜像

目录 1、使用mysql:5.6和 owncloud 镜像&#xff0c;构建一个个人网盘。 &#xff08;1&#xff09;下载mysql:5.6和owncloud镜像 &#xff08;2&#xff09;创建启动mysql:5.6和owncloud容器 &#xff08;3&#xff09;在浏览器中输入网盘服务器的IP地址&#xff0c;进行账…...

2023 CCPC 华为云计算挑战赛 hdu7401 流量监控(树形dp)

题目 流量监控 - HDU 7401 - Virtual Judge 简单来说&#xff0c;T(T<20)组样例&#xff0c;sumn不超过2e4 每次给定一棵n(n<2000)个点的树&#xff0c;两问&#xff1a; ①将n个点恰拆成n/2个pair(u,v)&#xff0c;要求一个点是另一个点的祖先&#xff0c;求方案数 …...

01.Django入门

1.创建项目 1.1基于终端创建Django项目 打开终端进入文件路径&#xff08;打算将项目放在哪个目录&#xff0c;就进入哪个目录&#xff09; E:\learning\python\Django 执行命令创建项目 F:\Anaconda3\envs\pythonWeb\Scripts\django-admin.exe&#xff08;Django-admin.exe所…...

亿赛通电子文档安全管理系统任意文件上传漏洞(2023-HW)

亿赛通电子文档安全管理系统任意文件上传漏洞 一、 产品简介二、 漏洞概述三、 影响范围四、 复现环境五、 漏洞复现小龙POC检测 免责声明&#xff1a;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接或者间接的后果…...

docker限制容器日志大小

文章目录 业务场景问题排查彻底解决 业务场景 我们公司做交通相关业务&#xff0c;我们部门主要负责信控服务&#xff0c;卖信号机的硬件产品和配套的信控平台 由于有部分小项目&#xff0c;可能只有几十个路口&#xff0c;客户预算有限&#xff0c;只给我们老旧的Windows ser…...

底层驱动实现数码管显示温湿度数值功能

开发板&#xff1a;STM32MP157A 温湿度传感器&#xff1a;si7006 显示器&#xff08;数码管&#xff09;&#xff1a;m74hc595 遇到的问题&#xff1a;循环采集温湿度传感器数值&#xff0c;并将数值发送给数码管的时候两者存在竞态关系&#xff0c;导致数码管显示亮度很暗 …...

03架构管理之测试管理

专栏说明&#xff1a;针对于企业的架构管理岗位&#xff0c;分享架构管理岗位的职责&#xff0c;工作内容&#xff0c;指导架构师如何完成架构管理工作&#xff0c;完成架构师到架构管理者的转变。计划以10篇博客阐述清楚架构管理工作&#xff0c;专栏名称&#xff1a;架构管理…...

30、devtools 依赖关于自动重启(自动加载页面)的知识

devtools 依赖关于自动重启的知识 ★ 自动重启 devtools会监控类加载路径中的文件&#xff08;尤其是*.class文件&#xff09;&#xff0c;只要这些文件发生了改变&#xff0c; devtools就会自动重启Spring Boot应用。▲ 不同工具触发自动重启的方式&#xff1a;Eclipse&…...

ES6 Promise/Async/Await使用

Promise应用 在工作中, 我们经常会遇到用异步请求数据, 查询一个结果, 然后把返回的参数放入到下一个执行的异步函数像这样: $.ajax({..., success(resp)>{$.ajax({..., resp.id, success(resp)>{$.ajax({..., resp.name success(resp)>{//多层嵌套的情况, 看着是不…...

pyqt使用QChartView绘制饼状图详解(QPieSeries)

pyqt使用QChartView绘制柱状图一、工程搭建二、QPieSeries详解1、核心概念2、主要功能和方法2.1、QPieSeries 的常用方法2.2、QPieSlice 的常用属性和方法3、关键点解释4、常见问题二、代码示例1、示例代码2、效果展示一、工程搭建 pyqt6QtCharts模块需要单独安装&#xff0c;…...

cv_unet_image-colorization模型压缩与量化:面向移动端的部署优化

cv_unet_image-colorization模型压缩与量化&#xff1a;面向移动端的部署优化 想把那个能把黑白照片变彩色的AI模型塞进手机里&#xff1f;这听起来挺酷&#xff0c;但实际操作起来&#xff0c;你会发现它又大又慢&#xff0c;手机根本跑不动。这就像你想把一台高性能游戏电脑…...

STM32F103C8T6 HAL库驱动HC-SR04:用输入捕获双通道模式,精准测距不翻车

STM32F103C8T6 HAL库双通道捕获HC-SR04&#xff1a;高精度测距的工程实践 在智能小车避障、工业液位检测等嵌入式应用中&#xff0c;超声波测距模块的稳定性直接决定系统可靠性。传统单通道捕获方案常因计数器溢出、中断响应延迟等问题导致测量误差&#xff0c;而双通道输入捕获…...

线程池:Java 并发编程的核心武器

线程池&#xff1a;Java 并发编程的"核心武器" 线程池是管理和复用线程的高级工具&#xff0c;它能显著提高程序性能&#xff0c;避免频繁创建和销毁线程的开销。 为什么需要线程池&#xff1f; 没有线程池的问题 // 传统方式&#xff1a;来一个任务创建一个线程 pub…...

紧急通知:2024年Q3起欧盟EDPS已将差分隐私实现纳入DPIA强制审查项——Python开发者必须立即核查的4个代码检查点

第一章&#xff1a;差分隐私合规性背景与EDPS新规解读随着欧盟数据保护监管体系持续演进&#xff0c;欧洲数据保护监督机构&#xff08;EDPS&#xff09;于2024年7月发布《关于匿名化与假名化技术在公共部门应用的指导意见》&#xff0c;首次将差分隐私&#xff08;Differentia…...

基于 Kinova Gen3 机械臂的家庭人机交互安全算法研究

随着服务机器人逐步进入家庭场景&#xff0c;人机交互&#xff08;HRI&#xff09;的安全性成为影响机器人普及的关键因素。相较于工业环境&#xff0c;家庭空间布局多变、人员活动随机&#xff0c;对机械臂的感知、规划与控制提出了更高要求。本文以7自由度Kinova Gen3机械臂为…...

SMUDebugTool:16核心独立调节与实时硬件监控的锐龙平台性能优化工具

SMUDebugTool&#xff1a;16核心独立调节与实时硬件监控的锐龙平台性能优化工具 【免费下载链接】SMUDebugTool A dedicated tool to help write/read various parameters of Ryzen-based systems, such as manual overclock, SMU, PCI, CPUID, MSR and Power Table. 项目地址…...

ExcelJS 实战手册:从零构建企业级Excel报表系统

1. ExcelJS入门&#xff1a;为什么选择它构建企业报表&#xff1f; 第一次接触ExcelJS时&#xff0c;我正为一个电商项目头疼——每天要生成近万条订单数据的报表。尝试过直接输出CSV&#xff0c;但客户坚持要带格式的Excel文件&#xff1b;用PHPExcel处理又遇到内存溢出。直到…...

HunyuanVideo-Foley命令行教程:infer.py参数详解与批量音效生成脚本编写

HunyuanVideo-Foley命令行教程&#xff1a;infer.py参数详解与批量音效生成脚本编写 1. 环境准备与快速部署 在开始使用HunyuanVideo-Foley进行音效生成前&#xff0c;我们需要确保环境已经正确部署。本教程基于RTX 4090D 24GB显存显卡和CUDA 12.4优化环境。 1.1 镜像启动与…...

电脑c盘变红了怎么清理?C盘清理工具与方法

电脑c盘变红了怎么清理&#xff1f;问题不难解决&#xff0c;关键是选对方法工具&#xff01;下面介绍实用的清理C盘方法&#xff0c;便于你解决C盘变红的问题哦&#xff01; 关于C盘清理工具&#xff0c;给大家安排一款针对C盘爆满的清理神器---Windows - Cleaner&#xff0c…...