面试题 33. 二叉搜索树的后序遍历序列
二叉搜索树的后序遍历序列
- 题目描述
- 示例
- 题解
- 递归
- 单调栈
题目描述
输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。
示例
参考以下这颗二叉搜索树:
5/ \2 6/ \1 3
输入: [1,6,3,2,5]
输出: false
示例 2:
输入: [1,3,2,6,5]
输出: true
题解
递归
后序遍历的最后一个元素为根节点,根据二叉搜索树的性质,根节点左边的元素都小于根节点,根节点右边的元素都大于根节点。因此,我们找到第一个大于根节点的位置 𝑖,那么 𝑖
右边的元素都应该大于根节点,否则返回 false。然后递归判断左右子树。
class Solution {
public:bool verifyPostorder(vector<int>& postorder) {function<bool(int, int)> dfs = [&](int l, int r) -> bool {if (l >= r) {return true;}int v = postorder[r];int i = l;while (i < r && postorder[i] < v) {++i;}for (int j = i; j < r; ++j) {if (postorder[j] < v) {return false;}}return dfs(l, i - 1) && dfs(i, r - 1);};return dfs(0, postorder.size() - 1);}
};
单调栈
后序遍历的顺序为“左、右、根”,如果从右往左遍历数组,那么顺序就变成“根、右、左”,根据二叉搜索树的性质,右子树所有节点值均大于根节点值。
因此,从右往左遍历数组,就是从根节点往右子树走,此时值逐渐变大,直到遇到一个递减的节点,此时的节点应该属于左子树节点。我们找到该节点的直接父节点,那么此后其它节点都应该小于该父节点,否则返回 false。然后继续遍历,直到遍历完整个数组。
此过程借助栈来实现,具体步骤如下:
- 首先初始化一个无穷大的父节点值 𝑚𝑥,然后初始化一个空栈。
- 接下来,从右往左遍历数组,对于每个遍历到的元素 𝑥
- 如果 𝑥大于 𝑚𝑥,说明当前节点不满足二叉搜索树的性质,返回 false。
- 否则,如果当前栈不为空,且栈顶元素大于 𝑥,说明当前节点为左子树节点,循环将栈顶元素出栈并赋值给 𝑚𝑥,直到栈为空或者栈顶元素小于等于 𝑥,然后将 𝑥入栈。
遍历结束后,返回 true。
class Solution {
public:bool verifyPostorder(vector<int>& postorder) {stack<int> stk;int mx = 1 << 30;reverse(postorder.begin(), postorder.end());for (int& x : postorder) {if (x > mx) {return false;}while (!stk.empty() && stk.top() > x) {mx = stk.top();stk.pop();}stk.push(x);}return true;}
};
相关文章:
面试题 33. 二叉搜索树的后序遍历序列
二叉搜索树的后序遍历序列 题目描述示例 题解递归单调栈 题目描述 输入一个整数数组,判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true,否则返回 false。假设输入的数组的任意两个数字都互不相同。 示例 参考以下这颗二叉搜索树&#…...
Web响应式设计———1、Grid布局
1、网格布局 Grid布局 流动网格布局是响应式设计的基础。它通过使用百分比而不是固定像素来定义网格和元素的宽度。这样,页面上的元素可以根据屏幕宽度自动调整大小,适应不同设备和分辨率。 <!DOCTYPE html> <html lang"en"> &l…...
ESP32开发进阶: 训练神经网络
一、网络设定 我们设定一个简单的前馈神经网络,其结构如下: 输入层:节点数:2,接收输入数据,每个输入样本包含2个特征,例如 {1.0, 0.0}, {0.0, 1.0} 等。 隐藏层:节点数:…...
全国区块链职业技能大赛国赛考题前端功能开发
任务3-1:区块链应用前端功能开发 1.请基于前端系统的开发模板,在登录组件login.js、组件管理文件components.js中添加对应的逻辑代码,实现对前端的角色选择功能,并测试功能完整性,示例页面如下: 具体要求如下: (1)有明确的提示,提示用户选择角色; (2)用户可看…...
直接插入排序算法详解
直接插入排序(Straight Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排…...
sql手动自增id
有时候在运维处理数据的时候,需要给某张表插入新的记录,那么需要知道最新插入数据的id,并在最新id的基础上加上id增长步长获取新的id,这个过程往往需要现将max出来加1,再手动补充到sql语句中,很麻烦,而且数据多的时候容易出错。有…...
10_TypeScript中的泛型
TypeScript中的泛型) 一、泛型的定义二、泛型函数三、泛型类:比如有个最小堆算法,需要同时支持返回数字和字符串两种类型。通过类的泛型来实现四、泛型接口五、泛型类 --扩展 把类作为参数类型的泛型类1、实现:定义一个 User 的类…...
Unity3D之TextMeshPro使用
文章目录 1. TextMeshPro简介2. TextMeshPro创建3. TextMeshPro脚本中调用4. TextMeshPro字体设置及中文支持过程中出现的一些问题 1. TextMeshPro简介 【官网文档】https://docs.unity.cn/cn/2020.3/Manual/com.unity.textmeshpro.html TextMeshPro 是 Unity 的最终文本解决…...
K8S 上部署 Prometheus + Grafana
文章目录 一、使用 Helm 安装 Prometheus1. 配置源2. 下载 prometheus 包3. 安装 prometheus4. 卸载 二、使用 Helm 安装 Grafana1. 配置源2. 安装 grafana3. 访问4. 卸载 一、使用 Helm 安装 Prometheus 1. 配置源 地址:https://artifacthub.io/packages/helm/pro…...
雷军的逆天改命与顺势而为
雷军年度演讲前,朋友李翔提了一个问题:雷军造车是属于顺势而为还是逆势而为?评论互动区有一个总结,很有意思,叫“顺势逆袭”。 大致意思是产业趋势下小米从手机到IOT再切入汽车,是战略的必然,不…...
Leetcode 11. 盛最多水的容器
Leetcode 11. 盛最多水的容器 Leetcode 11. 盛最多水的容器 一、题目描述二、我的想法 一、题目描述 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。 找出其中的两条线,使得它们与 x 轴共同构成…...
Java笔试分享
1、设计模式(写>3种常用的设计模式) 设计模式是在软件工程中解决常见问题的经验性解决方案。以下是一些常用的设计模式: 单例模式(Singleton): 意图:确保一个类只有一个实例,并…...
LeetCode:对称的二叉树(C语言)
1、问题概述:给一个二叉树,看是否按轴对称 2、示例 示例 1: 输入:root [1,2,2,3,4,4,3] 输出:true 示例 2: 输入:root [1,2,2,null,3,null,3] 输出:false 3、分析 (1&a…...
Postman中的API Schema验证:确保响应精准无误
Postman中的API Schema验证:确保响应精准无误 在API开发和测试过程中,验证响应数据的准确性和一致性是至关重要的。Postman提供了一个强大的功能——API Schema验证,它允许开发者根据预定义的JSON Schema来检查API响应。本文将详细介绍如何在…...
深入浅出WebRTC—GCC
GoogCcNetworkController 是 GCC 的控制中心,它由 RtpTransportControllerSend 通过定时器和 TransportFeedback 来驱动。GoogCcNetworkController 不断更新内部各个组件的状态,并协调组件之间相互配合,向外输出目标码率等重要参数࿰…...
leetcode日记(49)旋转链表
其实不难,就是根据kk%len判断需要旋转的位置,再将后半段接在前半段前面就行。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : …...
InteliJ IDEA最新2024版下载安装与快速配置激活使用教程+jdk下载配置
第一步:下载ideaIC-2024.1.4 方法1:在线链接 IntelliJ IDEA – the Leading Java and Kotlin IDE (jetbrains.com) 选择社区版进行下载 方法2:百度网盘 链接:https://pan.baidu.com/s/1ydS6krUX6eE_AdW4uGV_6w?pwdsbfm 提取…...
【23】Android高级知识之Window(四) - ThreadedRenderer
一、概述 在上一篇文章中已经讲了setView整个流程中,最开始的addToDisplay和WMS跨进程通信的整个过程做了什么。继文章Android基础知识之Window(二),这算是另外一个分支了,接着讲分析在performTraversals的三个操作中,最后触发pe…...
Java-根据前缀-日期-数字-生成流水号(不重复)
🎈边走、边悟🎈迟早会好 小伙伴们在日常开发时可能会遇到的业务-生成流水号,在企业中可以说是比较常见的需求, 可以采用"前缀日期数字"的方式(ps:此方式是需要用到缓存的)前缀:为了…...
跟李沐学AI:卷积层
从全连接层到卷积 多层感知机十分适合处理表格数据,其中行对应样本,列对应特征。但对于图片等数据,全连接层会导致参数过多。卷积神经网络(convolutional neural networks,CNN)是机器学习利用自然图像中一…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP
编辑-虚拟网络编辑器-更改设置 选择桥接模式,然后找到相应的网卡(可以查看自己本机的网络连接) windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置,选择刚才配置的桥接模式 静态ip设置: 我用的ubuntu24桌…...
音视频——I2S 协议详解
I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议,专门用于在数字音频设备之间传输数字音频数据。它由飞利浦(Philips)公司开发,以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
企业大模型服务合规指南:深度解析备案与登记制度
伴随AI技术的爆炸式发展,尤其是大模型(LLM)在各行各业的深度应用和整合,企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者,还是积极拥抱AI转型的传统企业,在面向公众…...
