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

算法第三十九天-验证二叉树的前序序列化

验证二叉树的前序序列化

题目要求

在这里插入图片描述
在这里插入图片描述

解题思路

方法一:栈
栈的思路是「自底向上」的想法。下面要结合本题是「前序遍历」这个重要特点。

我们知道「前序遍历」是按照「根节点-左子树-右子树」的顺序遍历的,只有当根节点的所有左子树遍历完成之后,才会遍历右子树。对于本题的输入,我们可以先判断「左子树」是否有效的,然后再判断「右子树」是否有效的,最后判断「根节点-左子树-右子树」是否为有效的。这个思路类似于递归,而把递归改写成循环时,就会使用「栈」,这就是本题使用「栈」的原因。

下面的重点是如何判断一棵子树是否有效?首先考虑最简单情况:怎么判断一个节点是叶子节点?很明显,当一个节点的两个孩子都是 "#"(空)的时候,该节点就是叶子节点。

在这里插入图片描述

当一个节点不是叶子节点的时候,那么它必定至少有一个孩子非空!有两种情况:

两个孩子都非"#"(空);
一个孩子为"#"(空),另一个孩子非"#"(空);
为了兼容这两个情况,我们想出了本题的一个重磅级的技巧:把有效的叶子节点使用 "#" 代替。 比如把 4## 替换成 # 。此时,叶子节点会变成空节点!

在这里插入图片描述

具体操作流程示例如下:

如输入:"9,3,4,#,#,1,#,#,2,#,6,#,#",当遇到 x,#,# 的时候,就把它变为 #

模拟一遍过程:

  1. [9,3,4,#,#] => [9,3,#],继续
  2. [9,3,#,1,#,#] => [9,3,#,#] => [9,#] ,继续
  3. [9,#2,#,6,#,#] => [9,#,2,#,#] => [9,#,#] => [#],结束

方法二:计算入度出度

背景知识:

  • 入度:有多少个节点指向它;
  • 出度:它指向多少个节点。

我们知道在树(甚至图)中,所有节点的入度之和等于出度之和。可以根据这个特点判断输入序列是否为有效的!

在一棵二叉树中:

  • 每个空节点( "#")会提供 0 个出度和 1 个入度。
  • 每个非空节点会提供 2 个出度和 1 个入度(根节点的入度是 0)。

我们只要把字符串遍历一次,每个节点都累加 diff = 出度 - 入度 。在遍历到任何一个节点的时候,要求diff >= 0,原因是还没遍历到该节点的子节点,所以此时的出度应该大于等于入度。当所有节点遍历完成之后,整棵树的 diff == 0

这里解释一下为什么下面的代码中 diff 的初始化为 1。因为,我们加入一个非空节点时,都会对 diff 先减去 1(入度),再加上 2(出度)。但是由于根节点没有父节点,所以其入度为 0,出度为 2。因此 diff 初始化为 1,是为了在加入根节点的时候,diff 先减去 1(入度),再加上 2(出度),此时 diff 正好应该是2.

代码

方法一:


class Solution(object): def isValidSerialization(self, preorder): stack = [] for node in preorder.split(','): stack.append(node) while len(stack) >= 3 and stack[-1] == stack[-2] == '#' and stack[-3] != '#': stack.pop(), stack.pop(), stack.pop() stack.append('#') return len(stack) == 1 and stack.pop() == '#' 

方法二:


class Solution(object): def isValidSerialization(self, preorder): nodes = preorder.split(',') diff = 1 for node in nodes: diff -= 1 if diff < 0: return Falseif node != '#': diff += 2 return diff == 0 

复杂度分析

方法一:

  • 时间复杂度: O ( N ) O(N) O(N)
  • 空间复杂度: O ( N ) O(N) O(N)

方法二:

  • 时间复杂度: O ( N ) O(N) O(N)
  • 空间复杂度: O ( 1 ) O(1) O(1)

参考

负雪明烛

相关文章:

算法第三十九天-验证二叉树的前序序列化

验证二叉树的前序序列化 题目要求 解题思路 方法一&#xff1a;栈 栈的思路是「自底向上」的想法。下面要结合本题是「前序遍历」这个重要特点。 我们知道「前序遍历」是按照「根节点-左子树-右子树」的顺序遍历的&#xff0c;只有当根节点的所有左子树遍历完成之后&#xf…...

Rust---复合数据类型之字符串与切片(2)

目录 字符串操作删除 (Delete)连接 (Concatenate)字符串转义前情回顾: Rust—复合数据类型之字符串(1) 字符串操作 删除 (Delete) 删除方法仅适用于 String 类型,分别是: pop(),remove(),truncate(),clear(),此外还有drain() 方法。 pop 方法:pop() 方法返回一个 O…...

iOS 应用内网络请求设置代理

主要通过URLSessionConfiguration 的connectionProxyDictionary 属性 为了方便其他同学使用&#xff0c;我们可以通过界面来进行设定&#xff08;是否开启代理、服务端、端口&#xff09;&#xff0c;从而达到类似系统上的设定 具体链接参考&#xff1a;为 iOS 网络请求设置代理…...

什么是MariaDB

2024年4月6日&#xff0c;周六晚上 今晚在Debian12上安装mysql时&#xff0c;运行后却发现是MariaDB MariaDB是一个开源的关系型数据库管理系统&#xff08;RDBMS&#xff09;&#xff0c;它是MySQL的一个分支和替代品。MariaDB由MySQL的原始开发者之一Michael "Monty&qu…...

【面试八股总结】传输控制协议TCP(三)

参考资料 &#xff1a;小林Coding、阿秀、代码随想录 一、TCP拥塞控制⭐ 1. 慢启动 – Slow Start 慢启动是指TCP连接刚建立&#xff0c;一点一点地提速&#xff0c;试探一下网络的承受能力&#xff0c;以免直接扰乱了网络通道的秩序。 慢启动算法&#xff1a; 初始拥塞窗口…...

今年过去了多少天?(switch)

//今年已经过去了几天&#xff1f; #include <stdio.h> int monthday(int year,int month){switch(month){case 1:return 31;case 2:if ((year % 4 0 && year % 100 ! 0)||year % 400 0){return 29;}else{return 28;}break;case 3:return 31;case 4:return 30;…...

提升团队工程交付能力,从“看见”工程活动和研发模式开始

作者&#xff1a;张裕、雅纯 理想中的研发团队应当具有以下特征&#xff1a; 总是工作在最高优先级的事项上 理想的研发团队能够识别并始终集中精力在当前最紧迫和最有价值的任务上。这需要团队具备出色的项目管理能力和决策能力&#xff0c;以便能够正确评估优先级&#xff0…...

前端学习之DOM编程案例:全选反选案例

代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>全选反选</title> </head> <body><input type"checkbox" id"all">全选<ul><li><…...

golang map

1.底层实现 2.如何解决hash冲突 3.扩容机制 4.无序 5.非线程安全 6.不可寻址 runtime/map.go 1.底层实现 底层基于hash表实现&#xff0c;实现有2个结构体hmap&#xff0c;bmap&#xff0c;map由若干个桶存储&#xff0c;每个桶存8个元素&#xff0c;使用链地址解决hash冲突 …...

设计模式:享元模式案例

让我们以游戏开发中的棋类游戏&#xff08;例如国际象棋&#xff09;为例来展示享元模式的代码实现。在这个例子中&#xff0c;棋子的类型是内部状态&#xff0c;而棋子的位置是外部状态。 Java 代码示例 import java.util.HashMap; import java.util.Map;// 享元接口 interf…...

pandas(day5)

一. 检测重复值 1.1 检测 data pd.read_csv("./teacher/订单数据.csv")检测行与行之前是否有重复值 data.drop_duplicates()检测 列是否有重复值出现&#xff0c; keep first 从前往后判定 &#xff0c; last是从后往前判定data.drop_duplicates(subset["产…...

如何注册midjourney账号

注册Midjourney账号比较简单&#xff0c;准备好上网工具&#xff0c;进入官网 Midjourney访问地址&#xff1a; https://www.midjourney.com/ 目前没有免费使用额度了&#xff0c;会员最低 10 美元/月&#xff0c;一般建议使用30美元/月的订阅方案。了解如何订阅可以查看订阅…...

探索数据结构:特殊的双向队列

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ &#x1f388;&#x1f388;养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属专栏&#xff1a;数据结构与算法 贝蒂的主页&#xff1a;Betty’s blog 1. 双向队列的定义 **双向队列(double‑ended queue)**是一种特殊的队列…...

16_I2C库函数

I2C库函数 1.void I2C_DeInit(I2C_TypeDef* I2Cx);2.void I2C_Init(I2C_TypeDef* I2Cx, I2C_InitTypeDef* I2C_InitStruct);3.void I2C_StructInit(I2C_InitTypeDef* I2C_InitStruct);4.void I2C_Cmd(I2C_TypeDef* I2Cx, FunctionalState NewState);5.void I2C_DMACmd(I2C_Type…...

十八、Rust gRPC 多 proto 演示

十八、Rust gRPC 多 proto 演示 网上及各官方资料&#xff0c;基本是一个 proto 文件&#xff0c;而实际项目&#xff0c;大多是有层级结构的多 proto 文件形式&#xff0c;本篇文章 基于此诉求&#xff0c;构建一个使用多 proto 文件的 rust grpc 使用示例。 关于 grpc 的实现…...

【Linux】Linux64位环境下编译32位报错skipping incompatible的解决办法

本文首发于 ❄️慕雪的寒舍 问题 如题&#xff0c;当我尝试在wsl2的ubuntu中使用-m32选项编译32位程序的时候&#xff0c;出现了下面的两种报错 ❯ g -m32 test.cpp -o test1 && ./test1 In file included from test.cpp:1: /usr/include/stdio.h:27:10: fatal error…...

vue指令v-model

<!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>vue指令v-model</title> </head>…...

CentOS安装MySQL数据库

一、更新yum源 #下载对应repo文件 wget -O CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-8.repo #清除缓存 yum clean all #生成新缓存 yum makecache #更新 yum update -y 二、安装MySQL #获取源 wget http://repo.mysql.com/mysql80-community-release-el7-3.…...

从B2B转向B2B2C模式:工业品牌史丹利百得的转型历程

图片来源&#xff1a;Twitter 在当今数据驱动的营销环境中&#xff0c;企业努力更好了解客户&#xff0c;并在整个客户旅程中提供个性化体验。史丹利百得&#xff08;Stanley Black & Decker&#xff09;是一家领先的工具和工业设备供应商&#xff0c;近年来开始重大转型。…...

Redis群集模式和rsync远程同步

一、Redis群集模式 1.1 概念 1.2 作用 1.2.1 Redis集群的数据分片 1.2.2 Redis集群的主从复制模型 1.3 搭建Redis 群集模式 1.3.1 开启群集功能 1.3.2 启动redis节点 1.3.3 启动集群 1.3.4 测试群集 二、rsync远程同步 2.1 概念 2.2 同步方式 2.3 备份的方式 2.4…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)

HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

【Linux】C语言执行shell指令

在C语言中执行Shell指令 在C语言中&#xff0c;有几种方法可以执行Shell指令&#xff1a; 1. 使用system()函数 这是最简单的方法&#xff0c;包含在stdlib.h头文件中&#xff1a; #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等

&#x1f50d; 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术&#xff0c;可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势&#xff0c;还能有效评价重大生态工程…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...

DingDing机器人群消息推送

文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人&#xff0c;点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置&#xff0c;详见说明文档 成功后&#xff0c;记录Webhook 2 API文档说明 点击设置说明 查看自…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...