当前位置: 首页 > 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)>{//多层嵌套的情况, 看着是不…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

【网络安全产品大调研系列】2. 体验漏洞扫描

前言 2023 年漏洞扫描服务市场规模预计为 3.06&#xff08;十亿美元&#xff09;。漏洞扫描服务市场行业预计将从 2024 年的 3.48&#xff08;十亿美元&#xff09;增长到 2032 年的 9.54&#xff08;十亿美元&#xff09;。预测期内漏洞扫描服务市场 CAGR&#xff08;增长率&…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Yolov8 目标检测蒸馏学习记录

yolov8系列模型蒸馏基本流程&#xff0c;代码下载&#xff1a;这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中&#xff0c;**知识蒸馏&#xff08;Knowledge Distillation&#xff09;**被广泛应用&#xff0c;作为提升模型…...

leetcode73-矩阵置零

leetcode 73 思路 记录 0 元素的位置&#xff1a;遍历整个矩阵&#xff0c;找出所有值为 0 的元素&#xff0c;并将它们的坐标记录在数组zeroPosition中置零操作&#xff1a;遍历记录的所有 0 元素位置&#xff0c;将每个位置对应的行和列的所有元素置为 0 具体步骤 初始化…...

【Linux】使用1Panel 面板让服务器定时自动执行任务

服务器就是一台24小时开机的主机&#xff0c;相比自己家中不定时开关机的主机更适合完成定时任务&#xff0c;例如下载资源、备份上传&#xff0c;或者登录某个网站执行一些操作&#xff0c;只需要编写 脚本&#xff0c;然后让服务器定时来执行这个脚本就可以。 有很多方法实现…...