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

【LeetCode】剑指 Offer(16)

目录

题目:剑指 Offer 33. 二叉搜索树的后序遍历序列 - 力扣(Leetcode)

题目的接口:

解题思路:

代码:

过啦!!!

写在最后:


题目:剑指 Offer 33. 二叉搜索树的后序遍历序列 - 力扣(Leetcode)

题目的接口:

class Solution {
public:bool verifyPostorder(vector<int>& postorder) {}
};

解题思路:

我一般做二叉树的遍历的题目,

用的都是递归法,

这里二叉搜索树有一个特点:左子树小于根节点,右子树大于根节点

我们就利用这个特性来判断数组是不是二叉搜索树的后序遍历。

大体思路就是判断:

左子树是否小于根节点,右子树是否大于根节点,

遍历过程中找到左子树和右子树的边界,

再以每个左子树和右子树作为子集,

递归遍历每一个子集,如果符合条件就返回 true,不符合就返回 false。

代码:

class Solution {
public:bool is_verifyPostorder(vector<int>& postorder, int left, int right){//数组遍历完了,返回trueif(left >= right){return true;}//保留最开始的左边界int init_left = left;//分割左子树和右子树int mid = 0;//如果左子树一直小于根,就会遍历到第一个右子树的节点while(postorder[left] < postorder[right]){left++;}//第一个右子树的几点(用来分割左右子树)mid = left;//如果右子树一直大于根,就会遍历到根节点while(postorder[left] > postorder[right]){left++;}//如果遍历到了根节点,证明这个子集是搜索二叉树的后序遍历//将该子集的左子树和右子树分割成两个子集,继续递归判断是否符合条件return left == right && is_verifyPostorder(postorder, init_left, mid - 1)&& is_verifyPostorder(postorder, mid, right - 1);}bool verifyPostorder(vector<int>& postorder) {return is_verifyPostorder(postorder, 0, postorder.size() - 1);}
};

过啦!!!

写在最后:

以上就是本篇文章的内容了,感谢你的阅读。

如果喜欢本文的话,欢迎点赞和评论,写下你的见解。

如果想和我一起学习编程,不妨点个关注,我们一起学习,一同成长。

之后我还会输出更多高质量内容,欢迎收看。

相关文章:

【LeetCode】剑指 Offer(16)

目录 题目&#xff1a;剑指 Offer 33. 二叉搜索树的后序遍历序列 - 力扣&#xff08;Leetcode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 写在最后&#xff1a; 题目&#xff1a;剑指 Offer …...

第三十九章 linux-并发解决方法二(互斥锁mutex)

第三十九章 linux-并发解决方法二&#xff08;互斥锁mutex&#xff09; 文章目录第三十九章 linux-并发解决方法二&#xff08;互斥锁mutex&#xff09;互斥锁的定义与初始化互斥锁的DOWN操作互斥锁的UP操作用count1的信号量实现的互斥方法还不是Linux下经典的用法&#xff0c;…...

脚本方式本地仓库jar包批量导入maven私服

脚本内容&#xff0c;将以下内容保存为mavenimport.sh&#xff0c;放置于需要上传的目录下&#xff0c;可以是顶层目录&#xff0c;或者某个分包的目录&#xff0c;若私服已有待上传的包&#xff0c;则执行会被替换 #!/bin/bash # copy and run this script to the root of th…...

【c++】引用的学习

引用的定义和声明 引用是一种别名&#xff0c;它允许使用与原变量相同的内存位置。在C中&#xff0c;引用是使用&符号来定义的。引用必须在定义时初始化&#xff0c;并且可以与原变量分别使用。 int a 10; int& b a; // 定义了一个引用b&#xff0c;它指向a引用的作用…...

linux 软件安装及卸载

1.联网在线安装及卸载ubuntu环境下&#xff1a;使用apt-get 工具apt-get install - 安装软件包apt-get remove - 移除&#xff08;卸载&#xff09;软件包CentOS环境下&#xff1a;使用yum工具 &#xff08;银河麒麟系统属于centos&#xff09;yum install - 安装软件包yum rem…...

XShell连接ubuntu20.04.LTS

1 下载XshellXShell官方下载地址打开XSHELL官方下载地址&#xff0c;我们可以选择【家庭和学校用户的免费许可证】&#xff0c;输入邮箱之后即可获得下载链接安装非常简单&#xff0c;跟着提示进行即可。2 连接ubuntu2.1 查看ubuntu的ip地址输入命令查看ip地址ifconfig刚开始可…...

【FPGA】Verilog:MSI/LSI 组合电路之解码器 | 多路分解器

写在前面&#xff1a;本章将理解编码器与解码器、多路复用器与多路分解器的概念&#xff0c;通过使用 Verilog 实现多样的解码器与多路分解器&#xff0c;通过 FPGA 并使用 Verilog 实现。 Ⅰ. 前置知识 0x00 解码器与编码器&#xff08;Decoder / Encoder&#xff09; 解码器…...

深入理解JDK动态代理原理,使用javassist动手写一个动态代理框架

文章目录一、动手实现一个动态代理框架1、初识javassist2、使用javassist实现一个动态代理框架二、JDK动态代理1、编码实现2、基本原理&#xff08;1&#xff09;getProxyClass0方法&#xff08;2&#xff09;总结写在后面一、动手实现一个动态代理框架 1、初识javassist Jav…...

一、策略模式的使用

1、策略模式定义&#xff1a; 策略模式&#xff08;Strategy Pattern&#xff09;定义了一组策略&#xff0c;分别在不同类中封装起来&#xff0c;每种策略都可以根据当前场景相互替换&#xff0c;从而使策略的变化可以独立于操作者。比如我们要去某个地方&#xff0c;会根据距…...

Verilog使用always块实现时序逻辑

这篇文章将讨论 verilog 中一个重要的结构---- always 块&#xff08;always block&#xff09;。verilog 中可以实现的数字电路主要分为两类----组合逻辑电路和时序逻辑电路。与组合逻辑电路相反&#xff0c;时序电路电路使用时钟并一定需要触发器等存储元件。因此&#xff0c…...

面向对象设计模式:行为型模式之迭代器模式

一、迭代器模式&#xff0c;Iterator Pattern aka&#xff1a;Cursor Pattern 1.1 Intent 意图 Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation. 提供一种按顺序访问聚合对象的元素而不公开其基…...

如何快速在企业网盘中找到想要的文件

现在越来越多的企业采用企业网盘来存储文档和资料&#xff0c;而且现在市面上的企业网盘各种各样。在使用企业网盘过程中&#xff0c;很多用户会问到企业网盘中如何快速搜索文件的问题。但是无论是“标签”功能还是普通的“关键词搜索”功能&#xff0c;都是单层级的&#xff0…...

香橙派5使用NPU加速yolov5的实时视频推理(二)

三、将best.onnx转为RKNN格式 这一步就需要我们进入到Ubuntu20.04系统中了&#xff0c;我的Ubuntu系统中已经下载好了anaconda&#xff0c;使用anaconda的好处就是可以方便的安装一些库&#xff0c;而且还可以利用conda来配置虚拟环境&#xff0c;做到环境与环境之间相互独立。…...

算法练习-二分查找(一)

算法练习-二分查找 1 代码实现 1.1 非递归实现 public int bsearch(int[] a, int n, int value) {int low 0;int high n - 1;while (low < high) {int mid (low high) / 2;if (a[mid] value) {return mid;} else if (a[mid] < value) {low mid 1} else {high …...

通用业务平台设计(五):预警平台建设

前言 在上家公司&#xff0c;随着业务的不断拓展(从支持单个国家单个主体演变成支持多个国家多个主体)&#xff0c;对预警的诉求越来越紧迫&#xff1b;如何保障业务的稳定性那&#xff1f;预警可以帮我们提前甄别风险&#xff0c;从而让我们可以在风险来临前将其消灭&#xff…...

Windows openssl-1.1.1d vs2017编译

工具&#xff1a; 1. perl&#xff08;https://strawberryperl.com/&#xff09; 2. nasm&#xff08;https://nasm.us/&#xff09; 3. openssl源码&#xff08;https://www.openssl.org/&#xff09; 可以自己去下载 或者我的网盘提供下载&#xff1a; 链接&#xff1a;…...

【深蓝学院】手写VIO第2章--IMU传感器--笔记

0. 内容 1. 旋转运动学 角速度的推导&#xff1a; 左ω∧\omega^{\wedge}ω∧&#xff0c;而ω\omegaω是在z轴方向运动&#xff0c;θ′[0,0,1]T\theta^{\prime}[0,0,1]^Tθ′[0,0,1]T 两边取模后得到结论&#xff1a; 线速度大小半径 * 角速度大小 其中&#xff0c;对旋转矩…...

网络基础(二)之HTTP与HTTPS

应用层 再谈 "协议" 协议是一种 "约定". socket api的接口, 在读写数据时, 都是按 "字符串" 的方式来发送接收的. 如果我们要传输一些"结构化的数据" 怎么办呢? 为什么要转换呢&#xff1f; 如果我们将struct message里面的信息…...

Python每日一练(20230306)

目录 1. 翻转二叉树 ★★ 2. 最长公共前缀 ★★ 3. 2的幂 ★ 1. 翻转二叉树 翻转一棵二叉树。 示例 1&#xff1a; 输入&#xff1a; 4/ \2 7/ \ / \ 1 3 6 9 输出&#xff1a; 4/ \7 2/ \ / \ 9 6 3 1示例 2&#xff1a; 输入&#xff1a; 1…...

C/C++每日一练(20230305)

目录 1. 整数分解 ☆ 2. 二叉树的最小深度 ★★ 3. 找x ★★ 1. 整数分解 输入一个正整数&#xff0c;将其按7进制位分解为各乘式的累加和。 示例 1&#xff1a; 输入&#xff1a;49 输出&#xff1a;497^2示例 2&#xff1a; 输入&#xff1a;720 输出&#xff1a;720…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

Java面试专项一-准备篇

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

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

嵌入式常见 CPU 架构

架构类型架构厂商芯片厂商典型芯片特点与应用场景PICRISC (8/16 位)MicrochipMicrochipPIC16F877A、PIC18F4550简化指令集&#xff0c;单周期执行&#xff1b;低功耗、CIP 独立外设&#xff1b;用于家电、小电机控制、安防面板等嵌入式场景8051CISC (8 位)Intel&#xff08;原始…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

边缘计算网关提升水产养殖尾水处理的远程运维效率

一、项目背景 随着水产养殖行业的快速发展&#xff0c;养殖尾水的处理成为了一个亟待解决的环保问题。传统的尾水处理方式不仅效率低下&#xff0c;而且难以实现精准监控和管理。为了提升尾水处理的效果和效率&#xff0c;同时降低人力成本&#xff0c;某大型水产养殖企业决定…...