二叉树 - 栈 - 计数 - leetcode 331. 验证二叉树的前序序列化 | 中等难度

在这里插入图片描述

题目 - 点击直达

  • leetcode 331. 验证二叉树的前序序列化 | 中等难度
    • 1. 题目详情
      • 1. 原题链接
      • 2. 基础框架
    • 2. 解题思路
      • 1. 题目分析
      • 2. 算法原理
        • 方法1:栈
        • 方法2:计数
      • 3. 时间复杂度
    • 3. 代码实现
      • 方法1:栈
      • 方法2:计数

leetcode 331. 验证二叉树的前序序列化 | 中等难度

1. 题目详情

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

例如,上面的二叉树可以被序列化为字符串 “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 < = p r e o r d e r . l e n g t h < = 104 1 <= preorder.length <= 104 1<=preorder.length<=104
preorder 由以逗号 “,” 分隔的 [0,100] 范围内的整数和 “#” 组成

1. 原题链接

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

2. 基础框架

● Cpp代码框架

class Solution {
public:
    bool isValidSerialization(string preorder) {

    }
};

2. 解题思路

1. 题目分析

( 1 ) (1) (1) 本题给出字符序列,判断该序列是否是二叉树的前序遍历。不允许创建二叉树。
( 2 ) (2) (2)
( 3 ) (3) (3)

2. 算法原理

方法1:栈

( 1 ) (1) (1) 槽位:一个槽位可以被看作 当前二叉树中正在等待被节点填充的那些位置。二叉树的建立也伴随着槽位数量的变化。
( 2 ) (2) (2) 每当遇到一个节点时:

  • 如果遇到了空节点,则要消耗一个槽位;
  • 如果遇到了非空节点,则除了消耗一个槽位外,还要再补充两个槽位。
方法2:计数

( 1 ) (1) (1) 借助栈时的时间复杂度是 O ( n ) O(n) O(n) , 空间复杂度是 O ( n ) O(n) O(n)
( 2 ) (2) (2) 可以不使用栈,而使用一个变量对槽位计数代替,空间复杂度降为 O ( 1 ) O(1) O(1)

3. 时间复杂度

方法1:栈 时间复杂度 O ( n ) O(n) O(n), 空间复杂度 O ( n ) O(n) O(n)

遍历一遍字符序列,最差情况是字符序列的 数字字符 和 逗号 交替,最终字符序列的一半元素会全部入栈且不出栈。

方法2:计数 时间复杂度 O ( n ) O(n) O(n) ,空间复杂度 O ( 1 ) O(1) O(1)

使用变量计数代替栈

3. 代码实现

方法1:栈

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.size();
        
        stack<int> st;
        int i = 0;
        st.push(1);
        while(i < n){
            if(st.empty()) return false;

            if(preorder[i] == ',') i++;
            else if(preorder[i] == '#'){
                st.top()--;
                if(st.top() == 0) st.pop();
                i++;
            }
            else{
                while(i < n && preorder[i] != ',') i++;
                st.top()--;
                if(st.top() == 0) st.pop();
                st.push(2);
            }
        }
        return st.empty();
    }
};

方法2:计数

class Solution {
public:
    bool isValidSerialization(string preorder) {
        int n = preorder.size();
        int i = 0;
        int slots = 1;
        while(i < n){
            if(slots == 0) return false;
            if(preorder[i] == ',') i++;
            else if(preorder[i] == '#'){
                slots--;
                i++;
            }
            else{
                while(i < n && preorder[i] != ',') i++;
                // slots--;
                // slots += 2;
                slots++;
            }
        }
        return slots == 0;
    }
};

T h e The The E n d End End

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

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

相关文章

免费Linux系统和生信宝典原创学习教程

免费Linux系统和生信宝典原创学习教程 生物信息的学习离不开Linux系统&#xff0c;不管自己写命令处理数据&#xff0c;还是使用现有的工具。Linux对我们来讲最重要的是它强大的命令行功能&#xff0c;可以快速、批量、灵活的处理数据的提取、统计和整理等耗时耗力的重复性工作…

CTF wed安全 (攻防世界)练习题

一、disabled_button 步骤一&#xff1a;进入网站发现按钮按不了 步骤二&#xff1a;按F12会查看源代码&#xff0c;会发现disabled disable属性 在HTML中&#xff0c; disabled 属性只有两个值&#xff1a;一个是不带值&#xff08;例如&#xff1a;disabled&#xff09;&…

4.2学习总结

一.java学习总结 (本次java学习总结,主要总结了抽象类和接口的一些知识,和它们之间的联系和区别) 一.抽象类 1.1定义: 抽象类主要用来抽取子类的通用特性&#xff0c;作为子类的模板&#xff0c;它不能被实例化&#xff0c;只能被用作为子类的超类。 2.概括: 有方法声明&…

【隐私计算实训营008——SCQL】

1.SCQL使用/集成最佳实践 目前SCQL只开放API供用户使用/集成 使用SCDBClient上手体验可以基于SCQL API开发封装白屏产品&#xff0c;或集成到业务链路中 1.1 部署系统 环境配置&#xff1a; 机器配置&#xff1a;CPU/MEM最低8C16G机构之间的网络互通 镜像&#xff1a;secret…

Redis实现高可用之持久化介绍

前言 在生产环境中&#xff0c;为了实现Redis的高可用性&#xff0c;可以采用持久化、主从复制、哨兵模式和 Cluster集群的方法确保数据的持久性和可靠性。这里首先介绍一下使用持久化实现服务器的高可用。 目录 一、Redis 高可用方法 1. 持久化 2. 主从复制 3. 哨兵 4.…

二轮电动自行车充电桩开源系统

文章目录 一、产品功能部分截图1.手机端&#xff08;小程序、安卓、ios&#xff09;2.PC端 二、小程序体验账号以及PC后台体验账号1.小程序体验账号2.PC后台体验账号关注公众号获取最新资讯 三、产品简介&#xff1f;1. 充电桩云平台&#xff08;含硬件充电桩&#xff09;&…

曲线降采样之道格拉斯-普克算法Douglas–Peucker

曲线降采样之道格拉斯-普克算法Douglas–Peucker 该算法的目的是&#xff0c;给定一条由线段构成的曲线&#xff0c;找到一条点数较少的相似曲线&#xff0c;来近似描述原始的曲线&#xff0c;达到降低时间、空间复杂度和平滑曲线的目的。 附赠自动驾驶学习资料和量产经验&…

【与C++的邂逅】---- 函数重载与引用

关注小庄 顿顿解馋(▿) 喜欢的小伙伴可以多多支持小庄的文章哦 &#x1f4d2; 数据结构 &#x1f4d2; C 引言 : 上一篇博客我们了解了C入门语法的一部分&#xff0c;今天我们来了解函数重载&#xff0c;引用的技术&#xff0c;请放心食用 ~ 文章目录 一. &#x1f3e0; 函数重…

windows搭建ftp实现局域网共享文件

一、开启ftp服务 1.使用 win Q 键&#xff0c;快捷打开搜索框 2.搜索框内搜索 “控制面板” 3. 进入控制面板内选择 ”程序“ 4. 单击进入 “启用或关闭windows功能” 5. 找到并展开“internet information services”、 6. 建议展开后全选 “FTP服务器” 和 “web管理工…

OpenHarmony实战:轻量系统芯片移植

本文从芯片适配的端到端视角&#xff0c;为芯片/模组制造商提供基于OpenHarmony的芯片适配指导。典型的芯片架构&#xff0c;例如cortex-m、risc-v系列都可以按照本文档进行适配移植。 约束与限制 本文档适用于OpenHarmony LTS 3.0.1及之前版本的轻量系统的适配。 说明&#…

Redis中的复制功能(三)

复制 服务器运行ID 除了复制偏移量和复制积压缓冲区之外&#xff0c;实现部分重同步还需要用到服务器运行ID(run ID): 1.每隔Redis服务器&#xff0c;不论主服务器还是从服务&#xff0c;都会有自己的运行ID2.运行ID在服务器启动时自动生成&#xff0c;由40个随机的十六进制…

ndk ffmpeg

报错&#xff1a; 解决办法&#xff1a; 报错 解决办法&#xff1a;

大模型量化技术-GPTQ

大模型量化技术-GPTQ 2022年,Frantar等人发表了论文 GPTQ:Accurate Post-Training Quantization for Generative Pre-trained Transformers。 这篇论文详细介绍了一种训练后量化算法,适用于所有通用的预训练 Transformer模型,同时只有微小的性能下降。 GPTQ算法需要通过…

vscode安装通义灵码

作为vscode的插件&#xff0c;直接使用 通义灵码-灵动指间&#xff0c;快码加编&#xff0c;你的智能编码助手 通义灵码&#xff0c;是一款基于通义大模型的智能编码辅助工具&#xff0c;提供行级/函数级实时续写、自然语言生成代码、单元测试生成、代码注释生成、代码解释、研…

性能测试?

一、什么是性能测试 先看下百度百科对它的定义 性能测试是通过自动化的测试工具模拟多种正常、峰值以及异常负载条件来对系统的各项性能指标进行测试。我们可以认为性能测试是&#xff1a;通过在测试环境下对系统或构件的性能进行探测&#xff0c;用以验证在生产环境下系统性…

苹果手表Apple Watch录了两个半小时的录音,却只能播放4秒,同步到手机也一样,还能修复好吗?

好多人遇到这个情况&#xff0c;用苹果手表Apple Watch录音&#xff0c;有的录1个多小时&#xff0c;有的录了3、4小时&#xff0c;甚至更长时间&#xff0c;因为手表没电&#xff0c;忘记保存等原因造成录音损坏&#xff0c;都是只能播放4秒&#xff0c;同步到手机也一样&…

Java8 Stream API全面解析——高效流式编程的秘诀

文章目录 什么是 Stream Api?快速入门流的操作创建流中间操作filter 过滤map 数据转换flatMap 合并流distinct 去重sorted 排序limit 限流skip 跳过peek 操作 终结操作forEach 遍历forEachOrdered 有序遍历count 统计数量min 最小值max 最大值reduce 聚合collect 收集anyMatch…

git源码泄露

Git 源码泄露 开发人员会使用 git 进行版本控制&#xff0c;对站点自动部署。但如果配置不当&#xff0c;可能会将 .git 文件夹直接部署到线上环境&#xff0c;这就引起了 git 泄露漏洞&#xff0c;我们可以利用这个漏洞直接获得网页源码。 确定是否存在泄漏 &#xff08;1&…

java项目基于Springboot和Vue的高校心理教育辅导系统的设计与实现

今天要和大家聊的是基于Springboot和Vue的高校心理教育辅导系统的设计与实现 &#xff01;&#xff01;&#xff01; 有需要的小伙伴可以通过文章末尾名片咨询我哦&#xff01;&#xff01;&#xff01; &#x1f495;&#x1f495;作者&#xff1a;李同学 &#x1f495;&…

大模型之路3:趟到了Llama-Factory,大神们请指点

各种AI工具和框架层出不穷&#xff0c;为开发者和研究者提供了前所未有的便利。当然了&#xff0c;也有困扰。尤其是对于动手能力越来越弱的中年油腻老程序员来说&#xff0c;更是难上加难。据说&#xff0c;嗯&#xff0c;据师弟说&#xff0c;说LlamaFactory凭借其独特的功能…