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

day52 ResNet18 CBAM

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

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

小智AI+MCP

什么是小智AI和MCP 如果还不清楚的先看往期文章 手搓小智AI聊天机器人 MCP 深度解析&#xff1a;AI 的USB接口 如何使用小智MCP 1.刷支持mcp的小智固件 2.下载官方MCP的示例代码 Github&#xff1a;https://github.com/78/mcp-calculator 安这个步骤执行 其中MCP_ENDPOI…...

内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献

Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译&#xff1a; ### 胃肠道癌症的发病率呈上升趋势&#xff0c;且有年轻化倾向&#xff08;Bray等人&#xff0c;2018&#x…...

2025-05-08-deepseek本地化部署

title: 2025-05-08-deepseek 本地化部署 tags: 深度学习 程序开发 2025-05-08-deepseek 本地化部署 参考博客 本地部署 DeepSeek&#xff1a;小白也能轻松搞定&#xff01; 如何给本地部署的 DeepSeek 投喂数据&#xff0c;让他更懂你 [实验目的]&#xff1a;理解系统架构与原…...