2024.3.31力扣每日一题——验证二叉树的前序序列化

2024-04-08 22:04

本文主要是介绍2024.3.31力扣每日一题——验证二叉树的前序序列化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

2024.3.31

      • 题目来源
      • 我的题解
        • 方法一 计数
        • 方法二 栈

题目来源

力扣每日一题;题序:331

我的题解

方法一 计数
  • 当只有一个节点并且是空节点,则表示是空树,是一个正确的序列化
  • 正确的序列化节点数必然是偶数个,若不是偶数个,则不是一个正确的序列化
  • 除了空树起始节点必然不可能是空节点
  • 一个正确的序列化,必然非空节点数量比空节点数量少1

时间复杂度:O(n)
空间复杂度:O(1)

public boolean isValidSerialization(String preorder) {//空树if(preorder.equals("#"))return true;String[] s=preorder.split(",");int n=s.length;//包含空节点的树必然有偶数个节点   除了空树起始节点必然不可能是空节点if(n%2==0||s[0].equals("#"))return false;int countNum=0;int countChar=0;for(int i=0;i<n;i++){String s1=s[i];if(!s1.equals("#")){countNum++;}else{countChar++;}//若前面已经是一个完整的树,后序还有节点,则必然不是一个有效的树的前序序列化if(i<n-1&&countChar==countNum+1)return false;}//树的非空节点数必然比空节点少一个if(countChar!=countNum+1)return false;return true;
}
方法二 栈

参考官方题解

时间复杂度:O(n)
空间复杂度:O(1)

public boolean isValidSerialization(String preorder) {int n = preorder.length();int i = 0;Deque<Integer> stack = new LinkedList<Integer>();stack.push(1);while (i < n) {if (stack.isEmpty()) {return false;}if (preorder.charAt(i) == ',') {i++;} else if (preorder.charAt(i) == '#'){int top = stack.pop() - 1;if (top > 0) {stack.push(top);}i++;} else {// 读一个数字while (i < n && preorder.charAt(i) != ',') {i++;}int top = stack.pop() - 1;if (top > 0) {stack.push(top);}stack.push(2);}}return stack.isEmpty();
}

有任何问题,欢迎评论区交流,欢迎评论区提供其它解题思路(代码),也可以点个赞支持一下作者哈😄~

这篇关于2024.3.31力扣每日一题——验证二叉树的前序序列化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/886523

相关文章

SpringBoot实现Kafka动态反序列化的完整代码

《SpringBoot实现Kafka动态反序列化的完整代码》在分布式系统中,Kafka作为高吞吐量的消息队列,常常需要处理来自不同主题(Topic)的异构数据,不同的业务场景可能要求对同一消费者组内的... 目录引言一、问题背景1.1 动态反序列化的需求1.2 常见问题二、动态反序列化的核心方案2.1 ht

SpringBoot项目中Redis存储Session对象序列化处理

《SpringBoot项目中Redis存储Session对象序列化处理》在SpringBoot项目中使用Redis存储Session时,对象的序列化和反序列化是关键步骤,下面我们就来讲讲如何在Spri... 目录一、为什么需要序列化处理二、Spring Boot 集成 Redis 存储 Session2.1

Java controller接口出入参时间序列化转换操作方法(两种)

《Javacontroller接口出入参时间序列化转换操作方法(两种)》:本文主要介绍Javacontroller接口出入参时间序列化转换操作方法,本文给大家列举两种简单方法,感兴趣的朋友一起看... 目录方式一、使用注解方式二、统一配置场景:在controller编写的接口,在前后端交互过程中一般都会涉及

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

如何配置Spring Boot中的Jackson序列化

《如何配置SpringBoot中的Jackson序列化》在开发基于SpringBoot的应用程序时,Jackson是默认的JSON序列化和反序列化工具,本文将详细介绍如何在SpringBoot中配置... 目录配置Spring Boot中的Jackson序列化1. 为什么需要自定义Jackson配置?2.

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Django序列化中SerializerMethodField的使用详解

《Django序列化中SerializerMethodField的使用详解》:本文主要介绍Django序列化中SerializerMethodField的使用,具有很好的参考价值,希望对大家有所帮... 目录SerializerMethodField的基本概念使用SerializerMethodField的

Jackson库进行JSON 序列化时遇到了无限递归(Infinite Recursion)的问题及解决方案

《Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursion)的问题及解决方案》使用Jackson库进行JSON序列化时遇到了无限递归(InfiniteRecursi... 目录解决方案‌1. 使用 @jsonIgnore 忽略一个方向的引用2. 使用 @JsonManagedR

Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)

《Python爬虫selenium验证之中文识别点选+图片验证码案例(最新推荐)》本文介绍了如何使用Python和Selenium结合ddddocr库实现图片验证码的识别和点击功能,感兴趣的朋友一起看... 目录1.获取图片2.目标识别3.背景坐标识别3.1 ddddocr3.2 打码平台4.坐标点击5.图