【Leetcode】331. 验证二叉树的前序序列化

文章目录

  • 题目
  • 思路
  • 代码
  • 复杂度分析
    • 时间复杂度
    • 空间复杂度
  • 结果
  • 总结

题目

题目链接🔗
序列化二叉树的一种方法是使用 前序遍历 。当我们遇到一个非空节点时,我们可以记录下这个节点的值。如果它是一个空节点,我们可以使用一个标记值记录,例如 #。
在这里插入图片描述
例如,上面的二叉树可以被序列化为字符串 " 9 , 3 , 4 , # , # , 1 , # , # , 2 , # , 6 , # , # " "9,3,4,\#,\#,1,\#,\#,2,\#,6,\#,\#" "9,3,4,#,#,1,#,#,2,#,6,#,#",其中 # \# # 代表一个空节点。

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

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

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

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

示例 1:
输入: p r e o r d e r = " 9 , 3 , 4 , # , # , 1 , # , # , 2 , # , 6 , # , # " preorder = "9,3,4,\#,\#,1,\#,\#,2,\#,6,\#,\#" preorder="9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: t r u e true true

示例 2:
输入: p r e o r d e r = " 1 , # " preorder = "1,\#" preorder="1,#"
输出: f a l s e false false

示例 3:
输入: p r e o r d e r = " 9 , # , # , 1 " preorder = "9,\#,\#,1" preorder="9,#,#,1"
输出: f a l s e false false

提示:

  • 1 ≤ p r e o r d e r . l e n g t h ≤ 1 0 4 1 \leq preorder.length \leq 10^4 1preorder.length104
  • p r e o r d e r preorder preorder 由以逗号 " , " "," "" 分隔的 [ 0 , 100 ] [0,100] [0,100] 范围内的整数和 “ # ” “\#” “#” 组成

思路

这道题要求验证给定的序列是否是正确的二叉树的前序序列化,而且不能重建树。可以使用迭代的方法来模拟整个过程。

可以观察到一个有效的二叉树序列化中,非空节点后面必然跟着两个 ′ # ′ '\#' #表示空节点,因为二叉树中的每个节点都有两个子节点(包括空节点)。所以可以遍历序列,当遇到一个非空节点时,记录之后的两个节点是否为 ′ # ′ '\#' #,如果是则继续遍历,否则返回 f a l s e false false。遍历完成后,如果指针指向了序列的末尾,则返回 t r u e true true,否则返回 f a l s e false false

代码

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int p = 0;
        return dfs(preorder, p) && p == preorder.size();
    }

    bool dfs(const string& preorder, int& p) {
        if (p == preorder.size()) {
            return false;
        }

        if (preorder[p] == '#') {
            if (p == preorder.size() - 1) p++;
            else p += 2;
            return true;
        }

        while (p < preorder.size() && preorder[p] != ',') p++;

        if (p == preorder.size()) return false;

        p += 1;

        return dfs(preorder, p) && dfs(preorder, p);
    }
};

复杂度分析

时间复杂度

遍历整个序列,时间复杂度为 O ( n ) O(n) O(n)

空间复杂度

递归调用的深度最坏情况下为 O ( n ) O(n) O(n)

结果

在这里插入图片描述

总结

使用了递归的方法,通过模拟二叉树的前序遍历来判断序列是否有效。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/506398.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Tidb和MySQL性能简单测试对比

一、单SQL性能对比 由于TiDB的并发能力优秀&#xff0c;但是单个SQL执行延迟较差&#xff0c;为了客观对比&#xff0c;所以只用1个线程来压测tidb和mysql&#xff0c;以观察延迟情况 二、并发SQL性能对比 TiDB:v6.5.2 MySQL:8.0.26 &#xff08;单机&#xff09; 三、结论 …

构建安全高效的用户登录系统:登录流程设计与Token验证详解

在当今数字化时代&#xff0c;用户登录系统是几乎所有在线服务的基础。然而&#xff0c;随着网络安全威胁的不断增加&#xff0c;设计一个安全可靠的登录系统变得至关重要。本文将深入探讨用户登录流程的设计原则以及Token验证的实现方式&#xff0c;带您了解如何构建安全高效的…

【MySQL笔记】行转列+列转行+行转列为什么用SUM()

文章目录 行转列思路实现行转列为什么要用SUM等聚合函数 列转行思路回顾下Union 实现列转行 Reference 行转列 思路 GROUP BY聚合函数 实现行转列 SELECT product_id,SUM(IF(store store1, price, NULL)) AS store1,SUM(IF(store store2, price, NULL)) AS store2,SUM(IF(…

Vulnhub:BROKEN: GALLERY

目录 信息收集 1、arp 2、nmap 3、nikto 4、whatweb WEB wen信息收集 目录扫描 进制转换 ssh登录 提权 信息收集 1、arp ┌──(root㉿ru)-[~/kali/vulnhub] └─# arp-scan -l Interface: eth0, type: EN10MB, M…

上位机图像处理和嵌入式模块部署(qmacvisual形状匹配)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 在qmacvisual软件当中&#xff0c;提供了两种模板匹配的方法。除了前面介绍的灰度匹配&#xff0c;就是今天讲的形状匹配。当然&#xff0c;对于使…

AI如何影响装饰器模式与组合模式的选择与应用

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》《MYSQL应用》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 &#x1f680; 转载自热榜文章&#xff1a;设计模式深度解析&#xff1a;AI如何影响…

【动手学深度学习】深入浅出深度学习之利用神经网络识别螺旋状数据集

目录 &#x1f31e;一、实验目的 &#x1f31e;二、实验准备 &#x1f31e;三、实验内容 &#x1f33c;1. 生成螺旋状数据集 &#x1f33c;2. 打印数据集 &#x1f33c;3. 编程实现 &#x1f33b;仿射层-Affine类 &#x1f33b;传播层-Sigmoid类 &#x1f33b;损失函数…

[数据结构初阶]堆的应用

各位读者老爷好&#xff0c;鼠鼠又来了捏&#xff01;鼠鼠上一篇博客介绍的堆&#xff0c;那么今天来浅谈以下堆的应用&#xff0c;那么好&#xff0c;我们先来看两个问题&#xff1a; 1.如果有一组乱序的数组数据&#xff0c;希望你将这组数组的数据排成升序或降序&#xff0c…

【Spring MVC】快速学习使用Spring MVC的注解及三层架构

&#x1f493; 博客主页&#xff1a;从零开始的-CodeNinja之路 ⏩ 收录文章&#xff1a;【Spring MVC】快速学习使用Spring MVC的注解及三层架构 &#x1f389;欢迎大家点赞&#x1f44d;评论&#x1f4dd;收藏⭐文章 目录 Spring Web MVC一: 什么是Spring Web MVC&#xff1…

大促销活动时期如何做好DDoS防护?

每一次活动大促带来的迅猛流量&#xff0c;对技术人而言都是一次严峻考验。如果在活动期间遭受黑产恶意DDoS攻击&#xff0c;无疑是雪上加霜。电商的特性是业务常态下通常不会遭受大流量DDoS攻击&#xff0c;且对延迟敏感&#xff0c;因此只需要在活动期间按需使用DDoS防护。本…

分享three.js实现乐高小汽车

前言 Web脚本语言JavaScript入门容易&#xff0c;但是想要熟练掌握却需要几年的学习与实践&#xff0c;还要在弱类型开发语言中习惯于使用模块来构建你的代码&#xff0c;就像小时候玩的乐高积木一样。 应用程序的模块化理念&#xff0c;通过将实现隐藏在一个简单的接口后面&a…

代码随想录第二十四天| 回溯算法P1 | ● 理论基础 ● 77.

● 理论基础 题目分类 什么是回溯法 回溯法也可以叫做回溯搜索法&#xff0c;它是一种搜索的方式。 在二叉树系列中&#xff0c;不止一次提到了回溯&#xff0c;如二叉树&#xff1a;以为使用了递归&#xff0c;其实还隐藏着回溯 (opens new window)。 回溯是递归的副产品&…

通过pymysql读取数据库中表格并保存到excel(实用篇)

本篇文章是通过pymysql将本地数据库中的指定表格保存到excel的操作。 这里我们假设本地已经安装了对应的数据库管理工具&#xff0c;里面有一个指定的表格&#xff0c;现在通过python程序&#xff0c;通过调用pymysql进行读取并保存到excel中。 关于数据库管理工具是Navicat P…

使用Python简单筛选excel表数据并写入到新表

文章目录 0 背景1 技术2 实现代码 0 背景 因为需要检索excel中的一些信息&#xff0c;把检索后的结果&#xff0c;写入到新表中。 符合筛选后的结果&#xff1a; 写入到的新表格数据&#xff1a; 1 技术 使用pandas库&#xff0c;读取excel表格的数据。然后对表格中的数据…

初始Java篇(JavaSE基础语法)(5)(类和对象(下))

个人主页&#xff08;找往期文章包括但不限于本期文章中不懂的知识点&#xff09;&#xff1a;我要学编程(ಥ_ಥ)-CSDN博客 目录 封装 访问限定符 封装扩展之包 自定义包 static成员 static修饰成员变量 static修饰成员方法 static成员变量初始化 内部类 对象的打…

leetcode131分割回文串

递归树 下面这个代码是遍历处所有的子串 #include <bits/stdc.h> using namespace std; class Solution { public:vector<vector<string>> vvs;vector<string> vs;vector<vector<string>> partition(string s) {dfs(0,s);return vvs;}vo…

使用Thymeleaf配置国际化页面

在国际化&#xff08;i18n&#xff0c;即 Internationalization 的缩写&#xff0c;其中“i”和“n”之间有18个字母&#xff09;的上下文中&#xff0c;Thymeleaf 和 Spring Boot 可以很容易地一起工作&#xff0c;以支持多种语言的页面显示。下面是如何在 Spring Boot 应用中…

Unix中的进程和线程-1

目录 1.如何创建一个进程 2.如何终止进程 2.2遗言函数 3.进程资源的回收 4.孤儿进程和僵尸进程 孤儿进程 (Orphan Process)&#xff1a; 僵尸进程 (Zombie Process)&#xff1a; 代码示例&#xff1a; 5. 进程映像的更新 在Linux中&#xff0c;进程和线程是操作系统进行工作调…

文件名目录名或卷标语法不正确:数据恢复策略与预防措施

一、文件名目录名或卷标语法不正确的现象 在日常使用电脑或移动设备时&#xff0c;我们经常会遇到“文件名目录名或卷标语法不正确”的错误提示。这种错误通常发生在尝试访问、修改或删除文件、目录或卷标时&#xff0c;系统会提示无法完成操作&#xff0c;因为文件名、目录名…

星云曲库测试报告

文章目录 一、项目介绍1.1项目背景1.2功能介绍 二、测试环境三、测试执行过程3.1功能测试3.1.1登录页面测试3.1.2歌曲列表页面测试3.1.3“我喜欢”页面测试3.1.4上传页面测试 3.2界面自动化测试3.2.1登录页面测试3.2.2歌曲列表页面测试3.2.3“我喜欢”页面测试3.2.4上传页面测试…