当前位置: 首页 > 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…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...