LeetCode:331. 验证二叉树的前序序列化(模拟 Java)

目录

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

题目描述:

实现代码与解析:

模拟

原理思路:


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

题目描述:

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

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

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

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

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

  • 例如它永远不会包含两个连续的逗号,比如 "1,,3" 。

注意:不允许重建树。

示例 1:

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

输出: true

示例 2:

输入: preorder = "1,#"

输出: false

示例 3:

输入: preorder = "9,#,#,1"

输出: false

提示:

  • 1 <= preorder.length <= 104
  • preorder 由以逗号 “,” 分隔的 [0,100] 范围内的整数和 “#” 组成

实现代码与解析:

模拟

class Solution {
    public boolean isValidSerialization(String preorder) {

        Stack<String> stk = new Stack<>();

        String[] cs = preorder.split(",");

        for (String s: cs) {
            stk.push(s);
            while (stk.size() >= 3 &&
                    stk.get(stk.size() - 1).equals("#") &&
                    stk.get(stk.size() - 2).equals("#") &&
                    !stk.get(stk.size() - 3).equals("#")) {
                stk.pop();
                stk.pop();
                stk.pop();
                stk.push("#");
            }
        }
        return stk.size() == 1 && stk.peek().equals("#");
    }
}

原理思路:

        设x为数字非#, 遍历,用栈存储,x##转换为#,注意用while循环,可能多次消除,像祖玛那样。最后栈里只剩一个“#”,说明是true。

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

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

相关文章

JAV八股--redis

如何保证Redis和数据库数据一致性 关于异步通知中消息队列和Canal的内容。 redisson实现的分布式锁的主从一致性 明天继续深入看这个系列问题 介绍IO复用模型

5个网络基础概念

说到网络&#xff0c;有五大基础概念是不得不提的&#xff0c;IP地址&#xff0c;子网掩码、网关、DHCP服务和PPPoE拨号&#xff0c;这些都是日常做电脑或路由器网络配置经常用到的&#xff0c;相信很多人都听过这些概念念&#xff0c;也知道都是一串串数字&#xff0c;但具体是…

远控桌面多任务并发文件保密传输

远程桌面文件传输是一个重要的功能&#xff0c;大多数远控都是用的桌面程序模式&#xff0c;利用系统自带复制粘贴拖拽文件拷贝功能&#xff0c;做一个ole调用对接&#xff0c;可以将很多控制权交给操作系统。 但我做的是浏览器版&#xff0c;浏览器是沙盒原理&#xff0c;为了…

指针的深入理解(五)

指针的深入理解&#xff08;五&#xff09; 文章目录 指针的深入理解&#xff08;五&#xff09;前言一.函数指针数组1.1函数指针的理解1.2函数指针的类型 二.转移表2.1转移表的概念2.2计算器2.3函数指针数组的应用 三.回调函数3.1回调函数的概念3.2回调函数的应用 四.指针知识…

力扣热题100_链表_142_环形链表 II

文章目录 题目链接解题思路解题代码 题目链接 142. 环形链表 II 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中…

网络以太网之(1)基础概念

网络以太网之(1)基础概念 Author: Once Day Date: 2024年4月1日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文档可参考专栏&#xff1a;通信网络技术_Once-Day的…

NB-IOT——浅谈NB-IOT及模块测试

浅谈NB-IOT及模块基本使用测试 介绍什么是NB-IOT&#xff1f;NB-IOT的特点 使用准备基本使用 总结 介绍 什么是NB-IOT&#xff1f; NB-IoT&#xff0c;即窄带物联网&#xff08;Narrowband Internet of Things&#xff09;&#xff0c;是一种低功耗广域物联网&#xff08;LPW…

计算机网络——数据链路层(流量传输与可靠传输机制)

计算机网络——数据链路层&#xff08;流量传输与可靠传输机制&#xff09; 流量传输与可靠传输机制流量控制可靠传输机制 停止-等待协议无差错情况接收并检测到差错状态确认丢失或迟到状态 停等协议的效率分析后退N帧协议&#xff08;Go-Back-N&#xff0c;简称GBN&#xff09…

在js中本地存储的数组如何转成对象

一、此方法仅适用一维数组&#xff1b; 二、效果图 使用后 三、js代码。 function gong(s){console.log(s);let data;let kk1;// 检查ask_id是否不为空 if (s.ask_id null ) { kk1}else{kk2let dd;dds.data;sessionStorage.setItem(wenda,JSON.stringify(dd[0]))window.l…

MyBatis主要的类层次结构(Mybatis工具类)

MyBatis主要的类层次结构 每一个MyBatis的应用程序都以一个SqlSessionFactory 对象的实例为核心 。 SqlSessionFactory对象的实例可以通过SqlSessionFactoryBuilder对象来获得 。 SqlSessionFactoryBuilder对象可以从 XML 配置文件中构建 SqlSessionFactory对象。 package…

Linux grep和find命令常用类型

1. grep命令的使用。 查找文件中符合条件的字符串或正则表达式&#xff0c;然后将含有范本样式的那一列显示出来。若不指定任何文件名称&#xff0c;或是给的文件名为-&#xff0c;则gerp命令会从标准输入设备读取数据。 用于测试的文件目录结构如下&#xff1a; 1.1 在单个文…

Vue项目登录页实现获取短信验证码的功能

之前我们写过不需要调后端接口就获取验证码的方法,具体看《无需后端接口,用原生js轻松实现验证码》这个文章。现在我们管理后台有个需求,就是登录页面需要获取验证码,用户可以输入验证码后进行登录。效果如下,当我点击获取验证码后能获取短信验证码: 这里在用户点击获取…

如何利用Geoserver将矢量数据发布成伪3D服务

目录 1.1、前言1.2、伪3D服务效果图1.3、数据准备1.4、基本原理1.5、完整的样式文件1.6、Geoserver中的操作 1.1、前言 本篇文章需要的Geoserver环境&#xff0c;Geoserver的情况请参考博文Geoserver简介、Geoserver安装部署操作请参考博文Geoserver安装部署、Geoserver基本操作…

初识CSS

目录 前言&#xff1a; CSS的介绍&#xff1a; CSS的发展&#xff1a; 1&#xff09;CSS1.0&#xff1a; 2)CSS2.0: 3)CSS2.1: 4&#xff09;CSS3&#xff1a; CSS特点&#xff1a; 1&#xff09;丰富的样式定义&#xff1a; 2&#xff09;易于设置和修改&#xff1a; 3&…

Datacom HCIP笔记-ISIS协议

IS中间系统&#xff08;路由器/运行了ISIS协议的设备&#xff09; ES终端系统(PC,PAD,print) 网络功能模型 ISO定义 事实标准 OSI TCP/IP 网络层(CLNP) (IS-IS) 网络…

代码随想录算法训练营第39天|62.不同路径 |63. 不同路径 II

代码随想录算法训练营第39天|62.不同路径 |63. 不同路径 II 详细布置 62.不同路径 本题大家掌握动态规划的方法就可以。 数论方法 有点非主流&#xff0c;很难想到。 https://programmercarl.com/0062.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84.html 视频讲解&#xff1a;https…

linux编辑器——vim使用方法

文章目录 linux编辑器——vim使用方法1. vim的基本概念2. vim的基本操作3. vim正常模式命令集4. vim末行模式命令集5. vim操作总结6.简单vim配置7.参考资料 linux编辑器——vim使用方法 vi/vim的区别简单点来说&#xff0c;它们都是多模式编辑器&#xff0c;不同的是vim是vi的…

配置 施耐德 modbusTCP 分布式IO子站 RPA0100

1. 总体步骤 2. 软件组态&#xff1a;在 Unity Pro 软件中创建编辑 PRA 模块工程 2.1 新建项目 模块箱硬件型号如下 点击 Unity Pro 软件左上方【新建】按钮&#xff0c;选择正确的 DIO 模块型号、背板型号 2.2 模块组态 2.2.1 拖拽添加模块 双击【配置】菜单下的【0&…

理解 SQL 数据添加:从基础到实践

引言&#xff1a; 在现代软件开发中&#xff0c;数据库是不可或缺的一部分。而 SQL 作为结构化查询语言的代表&#xff0c;广泛应用于数据库管理系统中&#xff0c;为我们提供了强大的数据管理和查询能力。 主题&#xff1a; 我们将从基础的 SQL INSERT INTO 语句开始&…

基于FPGA的HDMI方块移动程序设计

前面写了一篇关于HDMI视频接口的文章《基于FPGA的HDMI视频接口的设计》&#xff0c;该文章对HDMI的相关知识点做了讲解&#xff0c;这里不再重复&#xff0c;本篇文章直接实现一个简单功能-方块的移动。 该系统程序主要实现的功能就是通过串口下发指令控制方块的位置移动&…