当前位置: 首页 > news >正文

【LeetCode: 331. 验证二叉树的前序序列化 + DFS】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

在这里插入图片描述

🍔 目录

    • 🚩 题目链接
    • ⛲ 题目描述
    • 🌟 求解思路&实现代码&运行结果
      • ⚡ DFS
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
    • 💬 共勉

🚩 题目链接

  • 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] 范围内的整数和 “#” 组成

🌟 求解思路&实现代码&运行结果


⚡ DFS

🥦 求解思路
  1. 通过递归按照先序来遍历的顺序来遍历二叉树,顺序为根-左-右。
  2. 递归函数的返回值为以当前节点为根的整个树的结束位置,递归拿到左子树的结束位置,再根据左子树递归返回的位置,拿到右子树的结束位置。
  3. 最后,判断为根的整棵树的结束位置是否等于数组中最后一个元素的位置。
  4. 有了基本的思路,接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {public boolean isValidSerialization(String preorder) {String[] arr = preorder.split(",");int index = process(arr, 0);return index == arr.length - 1 && index != -1;}public int process(String[] arr, int index) {if (index >= arr.length)return -1;if (arr[index].equals("#"))return index;int left = process(arr, index + 1);if (left == -1)return -1;int right = process(arr, left + 1);return right;}
}
🥦 运行结果

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

相关文章:

【LeetCode: 331. 验证二叉树的前序序列化 + DFS】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…...

【Consul】Linux安装Consul保姆级教程

【Consul】Linux安装Consul保姆级教程 大家好 我是寸铁&#x1f44a; 总结了一篇【Consul】Linux安装Consul保姆级教程✨ 喜欢的小伙伴可以点点关注 &#x1f49d; 前言 今天要把编写的go程序放到linux上进行测试Consul服务注册与发现&#xff0c;那怎么样才能实现这一过程&am…...

pytorch常用的模块函数汇总(1)

目录 torch&#xff1a;核心库&#xff0c;包含张量操作、数学函数等基本功能 torch.nn&#xff1a;神经网络模块&#xff0c;包括各种层、损失函数和优化器等 torch.optim&#xff1a;优化算法模块&#xff0c;提供了各种优化器&#xff0c;如随机梯度下降 (SGD)、Adam、RMS…...

素数的计数律:Π函数、歪斜数

相当多的数字&#xff01; 一、说明 自从人类开始掌握最起码的算术概念以来&#xff0c;有一类数字一直处于最前沿——素数。素数定义简单&#xff0c;但难以捕捉&#xff0c;众所周知&#xff0c;素数是数学中一些最困难问题的罪魁祸首&#xff0c;让几代最优秀的数学家感到…...

图像识别在农业领域的应用

图像识别技术在农业领域的应用正在逐渐成熟&#xff0c;它通过分析处理拍摄的植物或农田的图像&#xff0c;为农业生产提供决策支持。以下是图像识别在农业中的一些关键应用&#xff1a; 病虫害检测&#xff1a;图像识别技术能够识别作物上的病斑、虫害或异常状况。通过比较高…...

【JavaSE】java刷题--数组练习

前言 本篇讲解了一些数组相关题目&#xff08;主要以代码的形式呈现&#xff09;&#xff0c;主要目的在于巩固数组相关知识。 上一篇 数组 讲解了一维数组和二维数组的基础知识~ 欢迎关注个人主页&#xff1a;逸狼 创造不易&#xff0c;可以点点赞吗~ 如有错误&#xff0c;欢迎…...

预处理、编译、汇编、链接过程

预处理、编译、汇编、链接过程 预处理 引入头文件 #include 展开宏定义 #define 处理条件编译指令 #ifdef 删除注释 添加行号 在Linux下可以使用gcc -E命令把hello.c文件预处理成hello.i文件。windows这些操作都集成在编译器visual studio这些里面了。 编译 进行语法分…...

3、Cocos Creator 节点和组件

目录 1、 节点和组件 2、 节点层级和显示顺序 3、坐标系和节点变换属性 坐标系 锚点 旋转 缩放 尺寸 4、 常用技巧 5、参考 1、 节点和组件 Cocos Creator 的工作流程是以组件式开发为核心的&#xff0c;组件式架构也称作 组件 — 实体系统&#xff08;或 Entity-C…...

【js刷题:数据结构数组篇之长度最小的子数组】

长度最小的子数组 一、题目二、方法1.暴力解法2.滑动窗口是什么滑动窗口的起始位置滑动窗口的结束位置代码展示 3.力扣刷题水果成篮题目思路代码 一、题目 给定一个含有 n 个正整数的数组和一个正整数 s &#xff0c;找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组&…...

大话设计模式之装饰模式

装饰模式&#xff08;Decorator Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许向现有对象动态地添加新功能&#xff0c;同时又不改变其结构。装饰模式通过将对象放入包装器中来实现&#xff0c;在包装器中可以动态地添加功能。 在装饰模式中&#xff0c;通常会有…...

国赛大纲解读

1. 第一部分,是针对5G基础知识的掌握,第二部分是人工智能基本算法的掌握,就是人工智能的应用,用5G+人工智能(AI算法)进行网络优化的问题,要有网络优化的基础知识,比如说:某个区域的覆盖问题,覆盖特别差,但有数据,覆盖电频,srp值这些数据给你,根据数据来判断是…...

设计模式(5):原型模式

一.原型模式 通过 n e w 产生一个对象需要非常繁琐的数据准备或访问权限&#xff0c;则可以使用原型模式。 \color{red}{通过new产生一个对象需要非常繁琐的数据准备或访问权限&#xff0c;则可以使用原型模式。} 通过new产生一个对象需要非常繁琐的数据准备或访问权限&#xf…...

【React】vite + react 项目,进行配置 eslint

安装与配置 eslint 1 安装 eslint babel/eslint-parser2 初始化配置 eslint3 安装 vite-plugin-eslint4 配置 vite.config.js 文件5 修改 eslint 默认配置 1 安装 eslint babel/eslint-parser npm i -D eslint babel/eslint-parser2 初始化配置 eslint npx eslint --init相关…...

Windows入侵排查

目录 0x00 前言 0x01 入侵排查思路 1.1 检查系统账号安全 1.2 检查异常端口、进程 1.3 检查启动项、计划任务、服务 0x00 前言 当企业发生黑客入侵、系统崩溃或其它影响业务正常运行的安全事件时&#xff0c;急需第一时间进行处理&#xff0c;使企业的网络信息系统在最短时…...

C语言每日一题

1.题目 二.分析 本题有两点需要注意的&#xff1a; do-while循环 &#xff1a;在判断while条件前先执行一次do循环static变量 &#xff1a;程序再次调用时static变量的值不会重新初始化&#xff0c;而是在上一次退出时的基础上继续执行。for( i 1; i < 3; i )将调用两次…...

TheMoon 恶意软件短时间感染 6,000 台华硕路由器以获取代理服务

文章目录 针对华硕路由器Faceless代理服务预防措施 一种名为"TheMoon"的新变种恶意软件僵尸网络已经被发现正在侵入全球88个国家数千台过时的小型办公室与家庭办公室(SOHO)路由器以及物联网设备。 "TheMoon"与“Faceless”代理服务有关联&#xff0c;该服务…...

人脸68关键点与K210疲劳检测

目录 人脸68关键点检测 检测闭眼睁眼 双眼关键点检测 计算眼睛的闭合程度&#xff1a; 原理: 设置阈值进行判断 实时监测和更新 拓展&#xff1a;通过判断上下眼皮重合程度去判断是否闭眼 检测嘴巴是否闭合 提取嘴唇上下轮廓的关键点 计算嘴唇上下轮廓关键点之间的距…...

【跟着GPT4学JAVA】异常篇

JAVA异常中的知识点 问&#xff1a; 介绍下JAVA中的异常有哪些知识点吧 答&#xff1a; Java中的异常处理是一个重要的知识点&#xff0c;主要包括以下内容: 异常体系&#xff1a;Java的异常类是Throwable类派生出来的&#xff0c;Throwable下有两个重要的子类&#xff1a;Err…...

Ubuntu上安装d4rl数据集

Ubuntu上安装d4rl数据集 D4RL的官方 github: https://github.com/Farama-Foundation/D4RL 一、安装Mujoco 1.1 官网下载mujoco210文件 如果装过可以跳过这步 链接&#xff1a;https://github.com/deepmind/mujoco/releases/tag/2.1.0 下载第一个文件即可。我这里是在windo…...

C++之STL整理(4)之set 用法(创建、赋值、增删查改)详解

C之STL整理&#xff08;4&#xff09;之set 用法&#xff08;创建、赋值、增删查改&#xff09;详解 注&#xff1a;整理一些突然学到的C知识&#xff0c;随时mark一下 例如&#xff1a;忘记的关键字用法&#xff0c;新关键字&#xff0c;新数据结构 C 的map用法整理 C之STL整理…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

【Linux】Linux 系统默认的目录及作用说明

博主介绍&#xff1a;✌全网粉丝23W&#xff0c;CSDN博客专家、Java领域优质创作者&#xff0c;掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域✌ 技术范围&#xff1a;SpringBoot、SpringCloud、Vue、SSM、HTML、Nodejs、Python、MySQL、PostgreSQL、大数据、物…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

第一篇:Liunx环境下搭建PaddlePaddle 3.0基础环境(Liunx Centos8.5安装Python3.10+pip3.10)

第一篇&#xff1a;Liunx环境下搭建PaddlePaddle 3.0基础环境&#xff08;Liunx Centos8.5安装Python3.10pip3.10&#xff09; 一&#xff1a;前言二&#xff1a;安装编译依赖二&#xff1a;安装Python3.10三&#xff1a;安装PIP3.10四&#xff1a;安装Paddlepaddle基础框架4.1…...

32单片机——基本定时器

STM32F103有众多的定时器&#xff0c;其中包括2个基本定时器&#xff08;TIM6和TIM7&#xff09;、4个通用定时器&#xff08;TIM2~TIM5&#xff09;、2个高级控制定时器&#xff08;TIM1和TIM8&#xff09;&#xff0c;这些定时器彼此完全独立&#xff0c;不共享任何资源 1、定…...