验证二叉树的前序序列化Python解法

article/2025/7/14 22:00:16

序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #

例如,上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#",其中 # 代表一个空节点。

给定一串以逗号分隔的序列,验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

你可以认为输入格式总是有效的

例如它永远不会包含两个连续的逗号,比如 "1,,3" 。
注意:不允许重建树。

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/verify-preorder-serialization-of-a-binary-tree
 

例:

输入: preorder = "9,3,4,#,#,1,#,#,2,#,6,#,#"输出: true

解析:

可以将‘#’符号看做叶子节点,而叶子节点相较于其他节点要多一。所以可以设置一个值初始为1,每增加一个非叶子结点就+1,而每出现一个叶子节点(#)就减一,如果符合前序遍历的规则,那么在遍历完之前不会为0,因为非叶子节点一定多余叶子节点(#)。而遍历完后一定为0,因为叶子节点(#)只多一个。

class Solution(object):def isValidSerialization(self, preorder):""":type preorder: str:rtype: bool"""   flag = 1  # 判断值for node in preorder.split(','):  # 将字符串中的','剔除。if flag == 0:  # 遍历完之前达到0说明不符合前序遍历规则return Falseif node == '#':  # “叶子节点”flag -= 1else:  # “非叶子节点”flag += 1return flag == 0  # 遍历完后的判断

 


http://chatgpt.dhexx.cn/article/BEs11Zbf.shtml

相关文章

7-1 前序序列创建二叉树

7-1 前序序列创建二叉树 编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以二叉链表存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,代表一棵空树。…

超容易理解的数据结构前序,中序和后序序列

今天听了我们数据结构老师讲三序序列,发现有很多同学不能根据二叉树推,特发此文讲解。 对于三序序列,我们可以选择构造一个表格并创造一个指针,将指针指于二叉树根结点,对应表格则如下所示,若某节点无左孩…

IIC通信协议详解[转载]

IIC的基本介绍 IIC的简介 IIC(Inter-Integrated Circuit)总线是一种由PHILIPS公司在80年代开发的两线式串行总线,用于连接微控制器及其外围设备。它是半双工通信方式。 IIC总线最主要的优点是其简单性和有效性。由于接口直接在组件…

IIC通信协议学习

1.IIC简介 IIC:Inter-Integrated Circuit(内部集成电路) 需要两个管脚:SDA、SCL SPI协议:一个主设备对多个从设备,每增加一个从设备,需要增加一个端口CS* 特点:速度较快&#xff…

IIC总线设计①——IIC通信协议

目录 一、IIC(Inter-Integrated Circuit)总线介绍 二、IIC协议 (一)IIC通信过程 (二)起始信号和停止信号 程序 (三)应答信号和非应答信号 程序 (四)数…

STM32基于IIC通信协议的OLED模块使用(详解)

目录 前言 一、项目内容 实验简介 二、IIC模块 1、IIC协议简介 2、物理层 3、协议层 4、硬件IIC代码配置 5、软件模拟IIC配置 1、起始信号与停止信号 2、从机应答信号 3、数据的有效性 4、数据传输 三、OLED模块 1、软件配置 2、OLED原理 1、OLED初始化函数 …

IIC 通信协议 (一)

目录 引言 IIC协议 1、历史 2、特点 3、信号线 4、主从关系 5、通信过程 6、协议规范 地址 1、器件地址 2、存储器地址 读写时序 1、写时序 1.1、单字节写时序 1.2、连续写时序 2、读时序 2.1、单字节读时序 2.2、连续读时序 参考声明 引言 这个专栏闲置好…

基础通信协议之 IIC (I2C) 详细讲解

IIC是当今嵌入式应用中最常见的串行通信协议之一。对比OneWire严苛的时序要求,SPI等更多的线缆要求,IIC处于一个折中的位置:不那么多的2根线缆的硬件要求,不那么复杂严苛的时序要求,便可进行多主多从的双向通信&#x…

IIC 通信协议 (二)

目录 引言 子模块设计 思路 单字节 IIC 发送模块 思路 Verilog 源码 多字节发送控制模块 思路 Verilog 源码 仿真 思路 test bench 仿真结果 参考声明 引言 本篇博文承接前文,继续做 IIC 通信协议 FPGA实现相关的内容。用Verilog 编写一个 IIC 通信控…

IIC通信协议(硬件实现IIC通信详解I)

IIC通信协议 什么是IIC协议协议层起始信号和停止信号数据的有效性 什么是IIC协议 I2C(Inter-Integrated Circuit)通讯协议是由 Phiilps 公司开发的两线式串行总线,用于连接微控制器及其外围设备。是微电子通信控制领域广泛采用的一种总线标准…

详解通信协议之IIC通信协议

详解通信协议之IIC通信协议 本文结合AT24C02对IIC通信协议原理进行了描述。 IIC通信协议(以AT24C02为例) IIC通讯协议(Inter-Integrated Circuit)是由 Philips 公司开发双向同步半双工串行总线,只需要两根线(SDA、SCL)即可在连接于总线上的器件之间传…

IIC(I2C)通信协议详解

简介 I2C 是飞利浦公司设计的,一种很常见的总线协议, I2C 使用两条线在主控制器和从机之间进行数据通信。一条是 SCL(串行时钟线),另外一条是SDA(串行数据线),这两条数据线需要接上拉电阻,总线空闲的时候 SCL 和 SDA …

IIC 通信协议

一、IIC 通信协议介绍 IIC(Inter-Integrated Circuit)总线是一种由PHILIPS公司开发的两线式串行总线,用于连接微控制器及其外围设备。 如今主要在服务器管理中使用,其中包括单个组件状态的通信。例如管理员可对各个组件进行查询,以管理系统…

三大通信协议(二):IIC通信协议

目录 1. 概念2. 硬件连接3. 数据传输协议3.1 开始信号3.2 地址位3.3 读写位(R/W)3.4 应答位(ACK / NACK)3.5 数据位(8Bit)3.6 停止信号 4. 软件编写4.1 初始化4.2 开始信号4.3 IIC发送一个字节数据4.4 IIC读…

IIC通信协议总结

(1)概述 I2C(Inter-Integrated Circuit BUS) 集成电路总线,该总线由NXP(原PHILIPS)公司设计,多用于主控制器和从器件间的主从通信,在小数据量场合使用,传输距离短,任意时…

IIC通信协议,搞懂这篇就够了

注:公众号后台发送 “IIC” 即可获取基于STM32上实现软件模拟IIC的完整代码。 I2C(IIC)属于两线式串行总线,由飞利浦公司开发用于微控制器(MCU)和外围设备(从设备)进行通信的一种总线,属于一主多从(一个主设备(Master),多个从设备…

IIC通讯协议

一、简介 IIC(Inter-integerted Circuit)集成电路总线,该通信协议由NXP(原PHILIPS)公司设计,多用于主控制器和从器件间的主从通信,在小数据量场景下使用,传输距离短,任意…

搜狗搜索正式接入微信公众号

搜狗搜索正式接入微信公众号 6月9日中午消息,搜狗搜索今日宣布正式接入微信公众号数据。用户将在搜狗搜索页面查询和浏览微信公众号文章。 据悉,在搜狗搜索框中输入微信公众号关键词,便可在搜索结果页中查看相关微信公众号的文章列表&#xf…

Python爬虫 selenium自动化 利用搜狗搜索爬取微信公众号文章信息

少年最好的地方就是:虽然嘴上说要放弃,心底却总会憋着一口气。——刘同 文章目录 一、需求和网页分析二、selenium爬虫一、需求和网页分析 URL:https://weixin.sogou.com/ 你是否有特别喜欢的一些公众号文章,比如说关于网易云热评的。 我那么多遗憾,那么多期盼,你知道…

RSS订阅微信公众号初探-feed43

🚀 优质资源分享 🚀 学习路线指引(点击解锁)知识定位人群定位🧡 Python实战微信订餐小程序 🧡进阶级本课程是python flask微信小程序的完美结合,从项目搭建到腾讯云部署上线,打造一…