LeetCode 428. Serialize and Deserialize N-ary Tree【树,BFS,DFS】困难
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。
为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。
由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。
序列化是指将一个数据结构转化为位序列的过程,因此可以将其存储在文件中或内存缓冲区中,以便稍后在相同或不同的计算机环境中恢复结构。
设计一个序列化和反序列化 N N N 叉树的算法。一个 N N N 叉树是指每个节点都有不超过 N N N 个孩子节点的有根树。序列化 / 反序列化算法的算法实现没有限制。你只需要保证 N N N 叉树可以被序列化为一个字符串并且该字符串可以被反序列化成原树结构即可。
例如,你需要序列化下面的 3-叉 树。

为 [1 [3[5 6] 2 4]]。你不需要以这种形式完成,你可以自己创造和实现不同的方法。
或者,您可以遵循 LeetCode 的层序遍历序列化格式,其中每组孩子节点由空值分隔。

例如,上面的树可以序列化为 [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
你不一定要遵循以上建议的格式,有很多不同的格式,所以请发挥创造力,想出不同的方法来完成本题。
示例 1:
输入: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出: [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
示例 2:
输入: root = [1,null,3,2,4,null,5,6]
输出: [1,null,3,2,4,null,5,6]
示例 3:
输入: root = []
输出: []
提示:
- 树中节点数目的范围是
[0, 10^4]. 0 <= Node.val <= 10^4- N N N 叉树的高度小于等于
1000 - 不要使用类成员 / 全局变量 / 静态变量来存储状态。你的序列化和反序列化算法应是无状态的。
类似题目:
- 449. 序列化和反序列化二叉搜索树
- 297. 二叉树的序列化与反序列化 困难
- 428. 序列化和反序列化 N 叉树 困难
解法 BFS+类似LeetCode层序遍历格式+StringJoiner
import java.util.StringJoiner;
class Codec {// Encodes a tree to a single string.public String serialize(Node root) {if (root == null) return "";StringJoiner sj = new StringJoiner(",");Deque<Node> queue = new ArrayDeque<>();queue.offer(root);sj.add(Integer.toString(root.val));sj.add(null);while (!queue.isEmpty()) {Node curr = queue.poll();for (Node node : curr.children) { // 将每个节点的子节点作为一组,由空值分隔sj.add(Integer.toString(node.val));queue.offer(node);}sj.add(null);}return sj.toString();}// Decodes your encoded data to tree.public Node deserialize(String data) {if (data.isEmpty()) return null;String[] tokens = data.split(",");Deque<Node> queue = new ArrayDeque<>();int index = 0;Node root = new Node(Integer.parseInt(tokens[index++]), new ArrayList<Node>());++index; // 跳过nullqueue.offer(root); while (!queue.isEmpty()) {Node curr = queue.poll();while (index < tokens.length) {if (tokens[index].equals("null")) {++index;break;}Node node = new Node(Integer.parseInt(tokens[index++]), new ArrayList<Node>());curr.children.add(node);queue.offer(node);}}return root;}
}
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)
当然,也可以选择类似JSON那样有层次的序列化格式。总之,序列化和反序列的题目很发散,各种解法都行。
相关文章:
LeetCode 428. Serialize and Deserialize N-ary Tree【树,BFS,DFS】困难
本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...
javascript | 变量、函数、属性的命名规则
javascript标识符的命名规则 变量、函数、属性的名字、或者函数的参数,都可称为标识符。标识符可以是按照下列格式规则组合起来的一个或者多个字符。 第一个字符必须是一个字母、下划线_、或美元符号$。数字不可以作为标识符的首字符。其他字符可以是数字、字母、…...
手写Ribbon基本原理
本文已收录于专栏 《中间件合集》 目录 概念说明什么是RibbonRibbon和Nginx负载均衡的区别 工作流程代码实现RibbonSDK发送请求端引入RibbonSDK和Nacos的依赖配置文件中填写负载均衡策略调用代码 接收请求端执行效果发送请求端接收请求端 总结提升 概念说明 什么是Ribbon Ribb…...
k8s集群中ETCD备份和恢复
文章目录 [toc]一、etcd 概述二、安装etcdctl工具三、kubeadm部署方式部署1)备份2)恢复四、定时备份 五、二进制部署备份1)备份2)恢复1、停止apiserver和etcd2、etcd_1恢复3、etcd_2恢复4、etcd_3恢复5、启动etcd和apiserver6、检…...
node版本问题
服务器下载下来的vue项目启动出现下列问题 npm ERR! path E:\vueEnv\app\node_modules\node-sass npm ERR! command failed npm ERR! command C:\Windows\system32\cmd.exe /d /s /c node scripts/build.js npm ERR! Building: C:\Program Files\nodejs\node.exe E:\vueEnv\ap…...
四)Stable Diffussion使用教程:图生图
这一篇来说说图生图。 除了文生图之外,SD常用的还有图生图模式。 图生图,顾名思义就是使用一张图去让AI生成自己喜欢的另一张图。 有时候我们有一张喜欢的图,但是希望换一种颜色方案,这时就可以通过图生图的方式去实现了&#…...
yolov7简化yaml配置文件
yolov7代码结构简单,效果还好,但是动辄超过70几个模块的配置文件对于想要对网络进行魔改的朋友还是不怎么友好的,使用最小的tiny也有77个模块 代码的整体结构简单,直接将ELAN结构化写成一个类就能像yolov5一样仅仅只有20几个模块&…...
pprof火焰图性能优化
pprof火焰图性能优化 火焰图(flame graph)是性能分析的利器,在go1.1之前的版本我们需要借助go-torch生成,在go1.1后go tool pprof集成了此功能,今天就来说说如何使用其进行性能优化 在你启动http server的地方直接加入导入: _ “net/http/pprof” 获取…...
Greenplum 查找数据目录占用最大的表
背景 社区中某同学提出问题: 某环境磁盘占用空间较大,于是想找到数据目录占用最大的表。使用常规查询找不出来,于是到数据目录下分析filenode,找到3个filenode占了400G。然而根据filenode从pg_class中确找不到对应的relfilenode。…...
Java 基于 SpringBoot 的酒店管理系统,附源码和数据库
博主介绍:✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W,Csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 文章目录 一、前言介绍二、系统结构三、系统详细实现3.1用户信息管理3.2会员信息管理3.3客房信息管理3.4收藏…...
LinkedList(4):多线程LinkedList 不安全情况
多线程不安全演示,线程越多,现象越明显,这边只启了四个线程。 package com.example.demo;import java.util.LinkedList; import java.util.UUID;public class LInkedListThread {public static void main(String[] args) {final LinkedList&…...
3D印刷电路板在线渲染查看工具
从概念上讲,这是有道理的,因为PCB印制电路板上的走线从一个连接到下一个连接的路线基本上是平面的。 然而,我们生活在一个 3 维世界中,能够以这种方式可视化电路以及相应的组件,对于设计过程很有帮助。本文将介绍KiCad…...
【mysql】出现 slow sql 问题及建议
文章目录 1. SQL 执行什么情况下会变慢?2. 影响 SQL 语句执行效率的主要因素有哪些?3. 慢 SQL 是如何拖垮数据库的?4. 最佳实践建议 1. SQL 执行什么情况下会变慢? ● 数据量增加:数据库中的数据量可能会逐渐增加&…...
element树形筛选
<el-inputv-model"projectName"placeholder"请输入名称"clearablemaxlength"10"clear"clearTree" /> <el-divider /> <el-treeref"tree"class"filter-tree":data"treeList":props"…...
打字侠:一款专业的中文打字网站
打字侠第一个正式版发布啦!!! 虽然离期望的样子还有一段路要走,不过能看到它正式发布,我还是很激动哟! 打字侠是一款面向中学生和大学生的在线打字软件,它通过合理的课程设计和精美的图形界面帮…...
C++ std::default_random_engine的使用
使用std::default_random_engine可生成不同分布的随机数,下面使用实例来说明其使用。 随机生成0-1间的实数 //利用当前时间生成的种子,可保证每次生成的值都不一样 unsigned seed std::chrono::system_clock::now().time_since_epoch().count(); std:…...
软件设计模式(二):工厂、门面、调停者和装饰器模式
前言 在这篇文章中,荔枝将会梳理软件设计模式中的四种:工厂模式、Facade模式、Mediator模式和装饰器Decorator模式。其中比较重要的就是工厂模式和装饰器模式,工厂模式在开发中使用的频数比较高。希望荔枝的这篇文章能讲清楚哈哈哈哈…...
pdf文件签名的问题解决
今天解决冲突的jar,结果出现下面的问题 java.lang.IllegalAccessError: tried to access method org.bouncycastle.asn1.DERNull.<init>()V from class com.itextpdf.text.pdf.security.PdfPKCS7at com.itextpdf.text.pdf.security.PdfPKCS7.getEncodedPKCS7…...
Node.js安装使用
目录 一、安装 Node.js二、环境变量配置三、npm常用命令 Node.js 是一个强大的运行时环境,它使您能够在服务器端运行 JavaScript 代码。它非常流行,用于构建 Web 应用程序、API 和各种后端服务。 一、安装 Node.js 1、访问 Node.js 官方网站。 在主页上…...
sql:SQL优化知识点记录(七)
(1)索引优化5 (2)索引优化6 (3)索引优化7 查询*, 百分号加右边,否则索引会失效 没建立索引之前都是全表扫描 没建立索引 建立索引: 建立索引 id是主键,他也…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
给网站添加live2d看板娘
给网站添加live2d看板娘 参考文献: stevenjoezhang/live2d-widget: 把萌萌哒的看板娘抱回家 (ノ≧∇≦)ノ | Live2D widget for web platformEikanya/Live2d-model: Live2d model collectionzenghongtu/live2d-model-assets 前言 网站环境如下,文章也主…...
Oracle11g安装包
Oracle 11g安装包 适用于windows系统,64位 下载路径 oracle 11g 安装包...
从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
