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

LeetCode 449. Serialize and Deserialize BST【树,BFS,DFS,栈】困难

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

序列化是将数据结构或对象转换为一系列位的过程,以便它可以存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串,并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

示例 1:

输入:root = [2,1,3]
输出:[2,1,3]

示例 2:

输入:root = []
输出:[]

提示:

  • 树中节点数范围是 [0, 10^4]
  • 0 <= Node.val <= 10^4
  • 题目数据 保证 输入的树是一棵二叉搜索树。

类似题目:

  • 449. 序列化和反序列化二叉搜索树
  • 297. 二叉树的序列化与反序列化 困难
  • 428. 序列化和反序列化 N 叉树 困难

二叉搜索树是一种特殊的二叉树,序列化和反序列化过程也可以直接使用「297. 二叉树的序列化与反序列化」中的方法,即实现上我们可以忽略「BST」这一条件,使用BFS或DFS、存储空节点来进行序列号和反序列化。由于点的数量是 1 e 4 1e4 1e4 ,最坏情况下是当BST成链时,会有较大的空间浪费。

但二叉搜索树的特殊之处在于其中序遍历是有序的,可以利用这一点来优化时间和空间复杂度。


解法 二叉搜索树+后序遍历+栈

给定一棵二叉树的「先序遍历」和「中序遍历」可以恢复这颗二叉树。给定一棵二叉树的「后序遍历」和「中序遍历」也可以恢复这颗二叉树。而对于二叉搜索树,给定「先序遍历」或者「后序遍历」,对其经过排序即可得到「中序遍历」。因此,仅对二叉搜索树做「先序遍历」或者「后序遍历」,即可达到序列化和反序列化的要求。此题解采用「后序遍历」的方法

  • 序列化时,只需要对二叉搜索树进行后序遍历(注意跳过空节点),再将数组编码成字符串即可。
  • 反序列化时,需要先将字符串解码成后序遍历的数组。在将后序遍历的数组恢复成二叉搜索树时,不需要先排序得到中序遍历的数组、再根据中序和后序遍历的数组来恢复二叉树,而可以根据有序性直接由后序遍历的数组恢复二叉搜索树——后序遍历得到的数组中,根结点的值位于数组末尾,左子树的节点均小于根节点的值,右子树的节点均大于根节点的值,可以根据这些性质设计递归函数恢复二叉搜索树。
public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {return postOrder(root, new StringBuilder()).toString();}private StringBuilder postOrder(TreeNode root, StringBuilder sb) {if (root != null) { // 可以不用存储空指针sb = postOrder(root.left, sb);sb = postOrder(root.right, sb);sb.append(String.valueOf(root.val) + ",");}return sb;}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {if (data.isEmpty()) return null;String[] arr = data.split(",");Deque<Integer> stack = new ArrayDeque<Integer>();int length = arr.length;for (int i = 0; i < length; ++i)stack.push(Integer.parseInt(arr[i]));return construct(Integer.MIN_VALUE, Integer.MAX_VALUE, stack);}// 使用栈和后序遍历重构二叉搜索树private TreeNode construct(int lower, int upper, Deque<Integer> stack) {// 当前元素超出范围,不能用作子树根节点的值if (stack.isEmpty() || stack.peek() < lower || stack.peek() > upper) return null;int val = stack.pop();TreeNode root = new TreeNode(val);root.right = construct(val, upper, stack);root.left = construct(lower, val, stack);return root;}
}

复杂度分析:

  • 时间复杂度: O ( n ) O(n) O(n) ,其中 n n n 是树的节点数。 s e r i a l i z e serialize serialize 需要 O ( n ) O(n) O(n) 时间遍历每个点。 d e s e r i a l i z e deserialize deserialize 需要 O ( n ) O(n) O(n) 时间恢复每个点
  • 空间复杂度: O ( n ) O(n) O(n) ,其中 n n n 是树的节点数。 s e r i a l i z e serialize serialize 需要 O ( n ) O(n) O(n) 空间用数组保存每个点的值,递归的深度最深也为 O ( n ) O(n) O(n) d e s e r i a l i z e deserialize deserialize 需要 O ( n ) O(n) O(n) 空间用数组保存每个点的值,递归的深度最深也为 O ( n ) O(n) O(n)

相关文章:

LeetCode 449. Serialize and Deserialize BST【树,BFS,DFS,栈】困难

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

嵌入式IDE(1):IAR中ICF链接文件详解和实例分析

最近在使用NXP的提供的MCUXPresso IDE&#xff0c;除了Eclipse固有的优点外&#xff0c;我觉得它最大的优点就是在链接脚本的生成上&#xff0c;提供了非常直观的GUI配置界面。但这个IDE仅仅支持NXP相关的产品&#xff0c;而且调试的性能在某些情况下并不理想。而我们用得比较多…...

分布式版本控制工具——git

✅<1>主页&#xff1a;&#xff1a;我的代码爱吃辣 &#x1f4c3;<2>知识讲解&#xff1a;Linux——git ☂️<3>开发环境&#xff1a;Centos7 &#x1f4ac;<4>前言&#xff1a;git是一个开源的分布式版本控制系统&#xff0c;可以有效、高速地处理从很…...

C基础-数组

1.一维数组的创建和初始化 int main() {// int arr1[10];int n 0;scanf("%d",&n);//int count 10;int arr2[n]; //局部的变量&#xff0c;这些局部的变量或者数组是存放在栈区的&#xff0c;存放在栈区上的数组&#xff0c;如果不初始化的话&#xff0c;默认…...

springboot项目配置flyway菜鸟级别教程

1、Flyway的工作原理 Flyway在第一次执行时&#xff0c;会创建一个默认名为flyway_schema_history的历史记录表&#xff0c;这张表会用来跟踪或记录数据库的状态&#xff0c;然后每次项目启动时都会自动扫描在resources/db/migration下的文件的版本号并且通过查询flyway_schem…...

成都精灵云初试

最近参加了成都精灵云的笔试与面试&#xff0c;岗位是c工程师。后面自己复盘了过程&#xff0c;初试部分总结如下&#xff0c;希望能对各位相进该公司以及面试C工程师的同学提供一些参考。这也是博主第一次参加面试&#xff0c;很多东西都还没准备&#xff0c;很多答得不好&…...

css relative 和absolute布局

1、relative和absolute内部的元素都是相对于父容器&#xff0c;若父容器没有指定为relative&#xff0c;则默认为整个文档视图空间&#xff0c;absolute可以重叠元素&#xff0c;relative则不行。relative意味着元素的任意属性如left和right都是相对于其他元素的。absolute则相…...

更健康舒适更科技的照明体验!书客SKY护眼台灯SUKER L1上手体验

低价又好用的护眼台灯是多数人的需求&#xff0c;很多人只追求功能性护眼台灯&#xff0c;显色高、无频闪、无蓝光等基础需求。但是在较低价格中很难面面俱到&#xff0c;然而刚发布的SUKER书客L1护眼台灯却是一款不可多得的性价比护眼台灯&#xff0c;拥有高品质光源&#xff…...

经管博士科研基础【19】齐次线性方程组

1. 线性方程组 2. 非线性方程组 非线性方程,就是因变量与自变量之间的关系不是线性的关系,这类方程很多,例如平方关系、对数关系、指数关系、三角函数关系等等。求解此类方程往往很难得到精确解,经常需要求近似解问题。相应的求近似解的方法也逐渐得到大家的重视。 3. 线…...

django报错解决 Forbidden (403) CSRF verification failed. Request aborted.

django报错解决 Forbidden (403) CSRF verification failed. Request aborted. 报错内容 Forbidden (403) CSRF verification failed. Request aborted.Help Reason given for failure:Origin checking failed - https://active-mantis-distinct.ngrok-free.app does not mat…...

k8s-实战——yapi平台部署

文章目录 k8s 部署yapi平台前言准备工作构建yapi镜像Dockerfileentrypoint.shbuild.sh源码下载构建镜像启动mongo数据库新建nfs服务mongo创建mongo服务初始化数据启动yapi服务创建yapi服务查看密码访问地址k8s 部署yapi平台 前言 部署yapi平台需要mo...

Excel VSTO开发5 -Excel对象结构

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 5 Excel对象结构 Excel提供了几个比较重要的对象&#xff1a; Application、Workbooks、Workbook、Worksheets、Worksheet 为了便…...

Javafx集成sqlite数据库

什么是SQLite SQLite是一款非常轻量级的关系数据库系统&#xff0c;支持多数SQL92标准。SQLite在使用前不需要安装设置&#xff0c;不需要进程来启动、停止或配置&#xff0c;而其他大多数SQL数据库引擎是作为一个单独的服务器进程&#xff0c;被程序使用某种内部进程通信(典型…...

react-native实现 TextInput 键盘显示搜索按钮并触发回调

<TextInput returnKeyType"search"returnKeyLabel"搜索"onSubmitEditing{e > {toSearch(keyword);}} /><SearchBarref{serachBarEl}placeholder"请输入"onChangeText{handleChangeSearch}value{search}onSubmitEditing{handleSearch…...

人大金仓分析型数据库备份和恢复(五)

增量备份 gpbackup和gprestore工具支持创建追加优化表的增量备份以及从增量备份还原。 只有表被更改时&#xff0c;增量备份才会备份所有指定的堆表和追加优化的表&#xff08;包括追加优化的&#xff0c;面向列的表&#xff09;。 例如&#xff0c;如果追加优化表的行已更改&a…...

lenovo联想笔记本ThinkPad P16V Gen 1(21FC,21FD)原装出厂Win11系统

原厂W11系统自带所有驱动、出厂主题壁纸、Office办公软件、联想电脑管家等预装程序 链接&#xff1a;https://pan.baidu.com/s/17dTExDSz-EDN4Qd-PZGJuw?pwdrgl3 提取码&#xff1a;rgl3 所需要工具&#xff1a;32G或以上的U盘 文件格式&#xff1a;ISO 文件大小…...

Django实现音乐网站 ⒃

使用Python Django框架制作一个音乐网站&#xff0c; 本篇主要是歌手详情页-专辑列表、专辑详情-单曲列表开发实现内容。 目录 歌手详情-专辑列表 路由设置 跳转设置 视图方法 模板内容 专辑详情-单曲列表 设置路由 视图处理并返回 模板渲染 分页优化 引入错误类型库…...

【开发问题系列】CSV转Excel

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kuan 的首页,持续学…...

mysql物理备份步骤

原库10.153.88.5&#xff0c;新建数据库实例10.153.88.6&#xff0c;注意/etc/my.cnf配置和88.5一致&#xff0c;测试目的是通过copy数据文件到88.6来恢复数据库。 在数据库10.153.88.5打包数据文件&#xff1a; [mysqlt3-dtpoc-dtpoc-web04 mysql]$ cd /testdata/mysql [mys…...

react使用hook封装一个tab组件

目录 react使用hook封装一个tab组件Tabbar.jsx使用组件效果 react使用hook封装一个tab组件 Tabbar.jsx import PropsTypes from "prop-types"; import React, { useEffect, useState } from react; export default function Tabbar(props) {const { tabData , cur…...

web vue 项目 Docker化部署

Web 项目 Docker 化部署详细教程 目录 Web 项目 Docker 化部署概述Dockerfile 详解 构建阶段生产阶段 构建和运行 Docker 镜像 1. Web 项目 Docker 化部署概述 Docker 化部署的主要步骤分为以下几个阶段&#xff1a; 构建阶段&#xff08;Build Stage&#xff09;&#xff1a…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

[ACTF2020 新生赛]Include 1(php://filter伪协议)

题目 做法 启动靶机&#xff0c;点进去 点进去 查看URL&#xff0c;有 ?fileflag.php说明存在文件包含&#xff0c;原理是php://filter 协议 当它与包含函数结合时&#xff0c;php://filter流会被当作php文件执行。 用php://filter加编码&#xff0c;能让PHP把文件内容…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

MySQL:分区的基本使用

目录 一、什么是分区二、有什么作用三、分类四、创建分区五、删除分区 一、什么是分区 MySQL 分区&#xff08;Partitioning&#xff09;是一种将单张表的数据逻辑上拆分成多个物理部分的技术。这些物理部分&#xff08;分区&#xff09;可以独立存储、管理和优化&#xff0c;…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...