二叉树 - 栈 - 计数 - leetcode 331. 验证二叉树的前序序列化 | 中等难度

题目 - 点击直达
- leetcode 331. 验证二叉树的前序序列化 | 中等难度
- 1. 题目详情
- 1. 原题链接
- 2. 基础框架
- 2. 解题思路
- 1. 题目分析
- 2. 算法原理
- 方法1:栈
- 方法2:计数
- 3. 时间复杂度
- 3. 代码实现
- 方法1:栈
- 方法2:计数
leetcode 331. 验证二叉树的前序序列化 | 中等难度
1. 题目详情
序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。
例如,上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#”,其中 # 代表一个空节点。
给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。
你可以认为输入格式总是有效的
例如它永远不会包含两个连续的逗号,比如 “1,3” 。
注意:不允许重建树。
示例 1:
输入: preorder = “9,3,4,#,#,1,#,#,2,#,6,#,#”
输出: true
示例 2:
输入: preorder = “1,#”
输出: false
示例 3:
输入: preorder = “9,#,#,1”
输出: false
提示:
1 < = p r e o r d e r . l e n g t h < = 104 1 <= preorder.length <= 104 1<=preorder.length<=104
preorder 由以逗号 “,” 分隔的 [0,100] 范围内的整数和 “#” 组成
1. 原题链接
leetcode 331. 验证二叉树的前序序列化
2. 基础框架
● Cpp代码框架
class Solution {
public:bool isValidSerialization(string preorder) {}
};
2. 解题思路
1. 题目分析
( 1 ) (1) (1) 本题给出字符序列,判断该序列是否是二叉树的前序遍历。不允许创建二叉树。
( 2 ) (2) (2)
( 3 ) (3) (3)
2. 算法原理
方法1:栈
( 1 ) (1) (1) 槽位:一个槽位可以被看作 当前二叉树中正在等待被节点填充的那些位置。二叉树的建立也伴随着槽位数量的变化。
( 2 ) (2) (2) 每当遇到一个节点时:
- 如果遇到了空节点,则要消耗一个槽位;
- 如果遇到了非空节点,则除了消耗一个槽位外,还要再补充两个槽位。
方法2:计数
( 1 ) (1) (1) 借助栈时的时间复杂度是 O ( n ) O(n) O(n) , 空间复杂度是 O ( n ) O(n) O(n) 。
( 2 ) (2) (2) 可以不使用栈,而使用一个变量对槽位计数代替,空间复杂度降为 O ( 1 ) O(1) O(1) 。
3. 时间复杂度
方法1:栈 时间复杂度 O ( n ) O(n) O(n), 空间复杂度 O ( n ) O(n) O(n)
遍历一遍字符序列,最差情况是字符序列的 数字字符 和 逗号 交替,最终字符序列的一半元素会全部入栈且不出栈。
方法2:计数 时间复杂度 O ( n ) O(n) O(n) ,空间复杂度 O ( 1 ) O(1) O(1)
使用变量计数代替栈
3. 代码实现
方法1:栈
class Solution {
public:bool isValidSerialization(string preorder) {int n = preorder.size();stack<int> st;int i = 0;st.push(1);while(i < n){if(st.empty()) return false;if(preorder[i] == ',') i++;else if(preorder[i] == '#'){st.top()--;if(st.top() == 0) st.pop();i++;}else{while(i < n && preorder[i] != ',') i++;st.top()--;if(st.top() == 0) st.pop();st.push(2);}}return st.empty();}
};
方法2:计数
class Solution {
public:bool isValidSerialization(string preorder) {int n = preorder.size();int i = 0;int slots = 1;while(i < n){if(slots == 0) return false;if(preorder[i] == ',') i++;else if(preorder[i] == '#'){slots--;i++;}else{while(i < n && preorder[i] != ',') i++;// slots--;// slots += 2;slots++;}}return slots == 0;}
};
T h e The The E n d End End
相关文章:
二叉树 - 栈 - 计数 - leetcode 331. 验证二叉树的前序序列化 | 中等难度
题目 - 点击直达 leetcode 331. 验证二叉树的前序序列化 | 中等难度1. 题目详情1. 原题链接2. 基础框架 2. 解题思路1. 题目分析2. 算法原理方法1:栈方法2:计数 3. 时间复杂度 3. 代码实现方法1:栈方法2:计数 leetcode 331. 验证二…...
Training language models to follow instructions with human feedback
Abstract 使语言模型变得更大并不意味着它们本身就能更好地遵循用户的意图。模型的输出结果可能存在以下问题 不真实有毒对用户没有帮助即这些模型没有和用户 “对齐”(aligned) 在给定的 Prompt 分布上,1.3B 的 InstructGPT 的输出比 175B GPT-3 的输出更好(尽管参数量相…...
Netty核心原理剖析与RPC实践11-15
Netty核心原理剖析与RPC实践11-15 11 另起炉灶:Netty 数据传输载体 ByteBuf 详解 在学习编解码章节的过程中,我们看到 Netty 大量使用了自己实现的 ByteBuf 工具类,ByteBuf 是 Netty 的数据容器,所有网络通信中字节流的传输都是…...
3.5网安学习第三阶段第五周回顾(个人学习记录使用)
本周重点 ①SSRF服务器端请求伪造 ②序列化和反序列化 ③Vaudit代码审计 本周主要内容 ①SSRF服务器端请求伪造 一、概述 SSRF: server site request forgery (服务器端请求伪造)。 SSR: 服务端请求,A服务器通过函数向B服务器发送请求。 SSRF发生的前提条件…...
kali常用命令功能简介记录
Kali Linux中常用的命令: 1. apt-get update:更新软件源列表。 2. apt-get upgrade:升级系统中已安装的软件包。 3. apt-get install [软件包]:安装指定的软件包。 4. apt-get remove [软件包]:卸载指定的软件包。 5.…...
低噪声、轨至轨运算放大器芯片—— D721、D722、D724,适合用于音频领域
应用领域 D721、D722、D724是我们推荐的三款低噪声、轨至轨运算放大器芯片,其中D721为单运放,D722为双运放,D724为四运放。适合用于音频领域、传感器等的信号放大处理,比如K歌宝、音响、测距、滤波器、AD转换器前级信号处理等等。…...
【统计】什么事 R 方
将线性模型拟合到时间序列时,通常使用最小二乘法在模型 y ^ ( t ) a b t \hat{y}(t) a bt y^(t)abt中找到系数 a a a和 b b b,其中 y ^ ( t ) \hat{y}(t) y^(t)是时间 t t t的预测值,而的观测值是 y ( t ) y(t) y(t)。 残差平方和又…...
Maplesoft Maple 2024(数学科学计算)mac/win
Maplesoft Maple是一款强大的数学计算软件,提供了丰富的功能和工具,用于数学建模、符号计算、数据可视化等领域的数学分析和解决方案。 Mac版软件下载:Maplesoft Maple 2024 for mac激活版 WIn版软件下载:Maplesoft Maple 2024特别…...
实战 | YOLOv8自定义数据集训练实现手势识别 (标注+训练+预测 保姆级教程--含数据集)
导 读 本文将手把手教你用YoloV8训练自己的数据集并实现手势识别。 安装环境 【1】安装torch, torchvision对应版本,这里先下载好,直接安装 pip install torch-1.13.1+cu116-cp38-cp38-win_amd64.whlpip install torchvision-0.14.1+cu116-cp38-cp38-win_amd64.whl 安装好…...
从零学算法2810
2810.你的笔记本键盘存在故障,每当你在上面输入字符 ‘i’ 时,它会反转你所写的字符串。而输入其他字符则可以正常工作。 给你一个下标从 0 开始的字符串 s ,请你用故障键盘依次输入每个字符。 返回最终笔记本屏幕上输出的字符串。 示例 1&am…...
Vue——案例01(查询用户)
目录 一、案例实现页面 二、案例实现效果 1. 查询效果 2. 年龄升序 3. 年龄降序 4. 原顺序 三、案例实现思路 四、完整代码 一、案例实现页面 实现用户对年龄的升降的排序、根据名字搜索用户信息以及重新返回原序列 二、案例实现效果 1. 查询效果 2. 年龄升序 3. 年龄…...
【数据结构】线性表
文章目录 前言线性表的定义和基本操作1.线性表的定义2.线性表的基本操作 顺序表的定义1.静态分配方式2.动态分配方式 顺序表的插入和删除1.顺序表的插入2.顺序表的删除 顺序表的查找1.按位查找(简单)2.按值查找 单链表的定义1.代码定义一个单链表2.不带头…...
983. 最低票价 C++
class Solution { public:int mincostTickets(vector<int>& days, vector<int>& costs) {// 状态定义: f[i] 表示 i 天及之后 旅行所需的最小花费int f[366]{};// 标注哪些天 出门for (int v: days) f[v] 1;// 由于状态转移是逆向的 所以倒序 …...
紫光展锐P7885核心板详细参数介绍_5G安卓智能模块开发方案
紫光展锐P7885核心板采用了先进的6nm EUV制程工艺,集成了高性能的应用处理器和金融级安全解决方案,为用户带来了全新的性能体验。 P7885核心板搭载了先进的6nm制程工艺SoC P7885,其中包含四核A76和四核A55,主频可达2.7Ghz…...
Keil MDK 5.37 及之后版本 安装 AC5(ARMCC) 编译器详细步骤
由于 Keil 5.37 及之后版本不再默认安装 AC5(ARMCC) 编译器,这就会导致由 AC5 编译的工程无法正常编译,往往输出窗口会提示以下信息:*** Target ‘STM32xxxx‘ uses ARM-Compiler ‘Default Compiler Version 5‘ which is not available. —…...
速盾:cdn配置ssl
CDN(Content Delivery Network)是一种内容分发网络,它的作用是将原始服务器上的内容分发到全球各地的边缘节点上,以提高用户访问速度和稳定性。随着数据传输的安全性要求越来越高,配置SSL(Secure Sockets L…...
代码随想录算法训练营 Day41 动态规划3
Day41 动态规划3 343. 整数拆分 思路 不知道如何拆分,才能使乘积最大化 有什么理论依据? 根据代码随想录 拆分使乘积最大化逻辑:应该尽可能拆成相同的数 根据题目,发现,拆分后的数可以继续拆分,因此可…...
面试题:反推B+树高度
一个表5000w数据,一个数据行大小为1k,主键为long类型数据,假设指针大小为8B,页大小为16K,求B树的高度? B树的非叶子节点存储key和指针,叶子节点存储数据,对应表中的某些行。 叶子节点…...
瑞吉外卖实战学习--11、分类管理的列表分页查询
分类管理的列表分页查询 前言1、创建接口2、基于分页组件来实现的 前言 通过前端接口可以看到请求和传递的参数,本文章是基于mybatisPlus的分页插件来实现的 1、创建接口 GetMapping("/page")public R<Page> page(int page,int pageSize){ // …...
网络安全新视角:数据可视化的力量
在当今数字化时代,网络安全已成为各大企业乃至国家安全的重要组成部分。随着网络攻击的日益复杂和隐蔽,传统的网络安全防护措施已难以满足需求,急需新型的解决方案以增强网络防护能力。数据可视化技术,作为一种将复杂数据转换为图…...
Prompt Tuning、P-Tuning、Prefix Tuning的区别
一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
跨链模式:多链互操作架构与性能扩展方案
跨链模式:多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈:模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展(H2Cross架构): 适配层…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
技术栈RabbitMq的介绍和使用
目录 1. 什么是消息队列?2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...
Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
