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

面试算法48:序列化和反序列化二叉树

题目

请设计一个算法将二叉树序列化成一个字符串,并能将该字符串反序列化出原来二叉树的算法。

分析

先考虑如何将二叉树序列化为一个字符串。需要逐个遍历二叉树的每个节点,每遍历到一个节点就将节点的值序列化到字符串中。以前序遍历的顺序遍历二叉树最适合序列化。如果采用前序遍历的顺序,那么二叉树的根节点最先序列化到字符串中,然后是左子树,最后是右子树。这样做的好处是在反序列化时最方便,从字符串中读出的第1个数值一定是根节点的值。

实际上,只把节点的值序列化到字符串中是不够的。首先,要用一个分隔符(如逗号)把不同的节点分隔开。其次,还要考虑如何才能在反序列化的时候构建不同结构的二叉树。

在这里插入图片描述
尽管null节点通常没有在图上画出来,但它们对树的结构是至关重要的。因此,应该把null节点序列化成一个特殊的字符串。如果把null节点序列化成"#“,那么图8.3(a)中的二叉树用前序遍历将被序列化成字符串"6,6,6,#,#,6,#,#,6,#,#”,而图8.3(b)中的二叉树将被序列化成字符串"6,6,#,#,6,6,#,#,6,#,#"。

public class Test {public static void main(String[] args) {TreeNode node6 = new TreeNode(6);TreeNode node66 = new TreeNode(6);TreeNode node666 = new TreeNode(6);TreeNode node6666 = new TreeNode(6);TreeNode node66666 = new TreeNode(6);node6.left = node66;node6.right = node666;node66.left = node6666;node66.right = node66666;String result = serialize(node6);System.out.println(result);TreeNode deserialize = deserialize(result);System.out.println(deserialize);}public static String serialize(TreeNode root) {if (root == null) {return "#";}String leftStr = serialize(root.left);String rightStr = serialize(root.right);return root.val + "," + leftStr + "," + rightStr;}public static TreeNode deserialize(String data) {String[] nodeStrs = data.split(",");int[] array = {0};return dfs(nodeStrs, array);}private static TreeNode dfs(String[] strs, int[] array) {String str = strs[array[0]];array[0]++;if (str.equals("#")) {return null;}TreeNode node = new TreeNode(Integer.valueOf(str));node.left = dfs(strs, array);node.right = dfs(strs, array);return node;}
}

相关文章:

面试算法48:序列化和反序列化二叉树

题目 请设计一个算法将二叉树序列化成一个字符串,并能将该字符串反序列化出原来二叉树的算法。 分析 先考虑如何将二叉树序列化为一个字符串。需要逐个遍历二叉树的每个节点,每遍历到一个节点就将节点的值序列化到字符串中。以前序遍历的顺序遍历二叉…...

【Python基础】Python编程入门自学笔记,基础大全,一篇到底!

📢:如果你也对机器人、人工智能感兴趣,看来我们志同道合✨ 📢:不妨浏览一下我的博客主页【https://blog.csdn.net/weixin_51244852】 📢:文章若有幸对你有帮助,可点赞 👍…...

windows自动登陆

新建文本粘贴下面代码,另存为注册表文件 Windows Registry Editor Version 5.00[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Driver Signing] "Policy"hex:00[HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Winlogon]"DefaultUserN…...

5G及其后的5G非地面网络:趋势和研究挑战-HARQ部分

NTN组件纳入5G架构第一步 在NTN SI中定义了一组架构选项。就NT部分而言,已确定了两大类:星载(即基于卫星的通信平台)和机载(即HAPS)设备 并行管理HARQ最大进程数 NHARQRTT(NTX−1)2μ NTX:传输…...

【WPF系列】- XAML语法规范

【WPF系列】- XAML语法规范 文章目录 【WPF系列】- XAML语法规范一、概述二、对象元素语法三、特性语法(属性)四、特性值的处理五、枚举特性值六、属性和事件成员名称引用七、属性元素语法八、集合语法九、XAML 内容属性XAML 内容属性值必须是连续的 十、…...

antv/g6之图布局及切换布局

一般图布局 目前为止,g6的一般图布局已经有13种了,如下: Random Layout:随机布局;Force2 Layout:G6 4.7.0 后支持力导向布局,与 gForce 相比性能更强;GForce Layout:G6 4.0 支持的…...

Wordpress plugin removes ‘/category‘

plugin removes /category from your category permalinks Remove Category URL – WordPress plugin | WordPress.org...

【大数据基础平台】星环TDH社区集群版本部署

🦄 个人主页——🎐开着拖拉机回家_大数据运维-CSDN博客 🎐✨🍁 🪁🍁🪁🍁🪁🍁🪁🍁 🪁🍁🪁&#x1f…...

【Java】汉诺塔

汉诺塔 汉诺塔(Tower of Hanoi)(河内塔):把圆盘从下面开始按大小顺序重新摆放到另一根柱子上,并且小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。 汉诺塔规则 disk表示圆盘数一次只…...

Java实现对Html文本的处理

1.引入jsoup <dependency><groupId>org.jsoup</groupId><artifactId>jsoup</artifactId><version>1.8.3</version> </dependency> 2. html示例 示例代码&#xff1a; <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1…...

Vue项目创建与启动(2023超详细的图文教程)

目录 一、下载node.js 二、下载vue-cli与webpack插件 三、项目初始化(项目配置详细信息) 四、项目启动 五、Vue项目工程结构&#xff08;扩展知识&#xff09; 一、下载node.js 1.检测是否已经安装过node.js 打开控制台,输入 npm -v如果有会显示对应版本 如果没有会显示…...

EtherCAT主站读取从站EEPROM抓包分析

0 工具准备 1.EtherCAT主站 2.EtherCAT从站&#xff08;本文使用步进电机驱动器&#xff09; 3.Wireshark1 抓包分析 1.1 报文总览 本文让主站去读取从站1字地址为0的EEPROM数据内容&#xff0c;主站读取从站EEPROM数据内容使用Wireshark抓包如下&#xff1a; 1.2 EEPROM读…...

Elasticsearch 8.X 如何生成 TB 级的测试数据 ?

1、实战问题 我只想插入大量的测试数据&#xff0c;不是想测试性能&#xff0c;有没有自动办法生成TB级别的测试数据&#xff1f;有工具&#xff1f;还是说有测试数据集之类的东西&#xff1f;——问题来源于 Elasticsearch 中文社区https://elasticsearch.cn/question/13129 2…...

汽车标定技术(四)--问题分析:多周期测量时上位机显示异常

目录 1.问题现象 2.数据流分析 ​​​​3.代码分析 3.1 AllocDAQ 3.2 AllocOdt 3.3 AllocOdtEntry 4.根因分析及解决方法 4.1 根因分析 4.2 解决方案 1.问题现象 在手撸XCP代码时&#xff0c; DAQ的实现是一大头痛的事情。最初单周期实现还好一点&#xff0c;特别是…...

Flink SQL时间属性和窗口介绍

&#xff08;1&#xff09;概述 时间属性&#xff08;time attributes&#xff09;&#xff0c;其实就是每个表模式结构&#xff08;schema&#xff09;的一部分。它可以在创建表的 DDL 里直接定义为一个字段&#xff0c;也可以在 DataStream 转换成表时定义。 一旦定义了时间…...

Tomcat免安装版修改标题名称和进程

tomcat免安装版启动后闪退问题 问题描述 在官网下载的tomcat免安装版的你安装完环境后发现启动闪退&#xff0c;tomcat启动依赖环境是JDK&#xff0c;所以需要tomcat对应版本的JDK支持。 tomcat8官网下载地址&#xff1a;https://tomcat.apache.org/ JDK环境官网下载地址&…...

vim搜索、替换tab

bibtex 中的缩进可能不一致&#xff0c;强迫症犯了想将&#xff1a; 缩进空格改 tab&#xff1b;行首的多个 tab 改为单个 参考 [1]&#xff0c;空格换 tab 可以&#xff1a; :set noexpandtab :%retab!行首的多个 tab 换单个&#xff1a; :%s/^\t\/\t/gReferences Replac…...

一文读懂ARM安全性架构和可信系统构建要素

一文读懂ARM安全性架构和可信系统构建要素 所谓可信系统&#xff08;trusted system&#xff09;&#xff0c;即能够用于保护密码和加密密钥等资产&#xff08;assets&#xff09;免受一系列的可信攻击&#xff0c;防止其被复制、损坏或不可用&#xff08;unavailable&#xf…...

Voice vlan、ICMP、单臂路由、mux-vlan

目录 一&#xff0c;Voice VLAN Voice vlan配置命令 一&#xff0c;问&#xff1a;已知网络中一台服务器的IP地址&#xff0c;如何找到这太服务器在哪台交换机的哪个接口上​编辑 思路&#xff1a; 二&#xff0c;ICMP协议 三&#xff0c;ICMP案例分析​编辑 四&#xf…...

TCP IP 网络编程(七) 理解select和epoll的使用

文章目录 理解select函数select函数的功能和调用顺序设置文件描述符设置监视范围及超时select函数调用示例 优于select的epoll基于select的I/O复用速度慢实现epoll时必要的函数和结构体epoll_createepoll_ctlepoll_wait基于epoll的服务器端 边缘触发和水平触发 理解select函数 …...

AFL++实战:从零开始用WSL搭建模糊测试环境(附libxml2案例)

AFL实战指南&#xff1a;WSL环境下的模糊测试从入门到精通 模糊测试&#xff08;Fuzz Testing&#xff09;作为软件安全测试的重要手段&#xff0c;近年来在漏洞挖掘领域展现出惊人的效果。对于Windows平台开发者而言&#xff0c;Windows Subsystem for Linux&#xff08;WSL&…...

基于Kubernetes Operator的MySQL InnoDB Cluster自动化部署实践

1. MySQL InnoDB Cluster与Kubernetes Operator基础 MySQL InnoDB Cluster是MySQL官方提供的高可用数据库解决方案&#xff0c;它基于MySQL Group Replication技术构建&#xff0c;能够实现多节点数据同步和自动故障转移。想象一下&#xff0c;这就像是一个由多个数据库实例组…...

从线索到成交,陀螺匠帮我打通了客户管理全流程

作为一个从业多年销售&#xff0c;我觉得我在管理客户过程中遇到的这些问题&#xff0c;很多企业多多少少也出现过。比如销售小王跟了一个月的客户&#xff0c;最后发现小李早就联系过了&#xff0c;经常白忙活&#xff1b;好不容易谈成的单子&#xff0c;合同改来改去&#xf…...

海康MVS软件从下载到实时预览:MV-CA013-21UC工业相机5分钟极速上手教程

海康MVS软件从下载到实时预览&#xff1a;MV-CA013-21UC工业相机5分钟极速上手教程 工业视觉系统正成为智能制造的核心组件&#xff0c;而海康威视MV-CA013-21UC工业相机凭借其高帧率、低噪声和稳定性能&#xff0c;在自动化检测、机器人引导等领域广受欢迎。本文将带您从零开…...

腾讯文档协作全攻略:从权限设置到区域锁定,团队办公效率翻倍

腾讯文档团队协作高阶指南&#xff1a;权限控制与区域锁定的艺术 在数字化办公时代&#xff0c;团队协作的效率往往决定了项目的成败。作为国内领先的在线协作文档工具&#xff0c;腾讯文档凭借其流畅的实时协作体验和丰富的权限管理功能&#xff0c;已经成为众多团队的首选工具…...

父子进程变量地址相同值却不同?图解Linux写时拷贝与页表机制

父子进程变量地址相同值却不同&#xff1f;图解Linux写时拷贝与页表机制 你是否曾在Linux环境下遇到过这样的现象&#xff1a;通过fork()创建的子进程与父进程打印同一个全局变量的地址时&#xff0c;两者的地址值完全相同&#xff0c;但实际读取的变量值却不同&#xff1f;这个…...

进程间通信(IPC):原理、场景与选型

在操作系统的世界里&#xff0c;进程是程序运行的基本单元&#xff0c;每个进程都拥有独立的内存空间和资源&#xff0c;彼此之间相互隔离&#xff0c;无法直接访问对方的数据。这种隔离机制保证了系统的稳定性&#xff0c;避免进程间相互干扰&#xff0c;但也带来了一个问题&a…...

小米智能家居与Home Assistant完美融合:打造高效智能家居生态

小米智能家居与Home Assistant完美融合&#xff1a;打造高效智能家居生态 【免费下载链接】ha_xiaomi_home Xiaomi Home Integration for Home Assistant 项目地址: https://gitcode.com/GitHub_Trending/ha/ha_xiaomi_home 小米智能家居Home Assistant集成是由小米官方…...

自建轻量CI_CD:GitHub Actions + Docker + 自动版本号 + 自动回滚 实战教程

自建轻量CI/CD&#xff1a;GitHub Actions Docker 自动版本号 自动回滚 实战教程 &#x1f3f7;️ 标签&#xff1a;CI/CD、GitHub Actions、Docker、自动化部署、自动版本号、自动回滚、DevOps &#x1f4cc; 阅读指南&#xff1a;本文手把手带你搭建一套轻量、免费、稳定的…...

LANDrop局域网文件传输:3分钟快速上手跨平台文件共享神器

LANDrop局域网文件传输&#xff1a;3分钟快速上手跨平台文件共享神器 【免费下载链接】LANDrop Drop any files to any devices on your LAN. 项目地址: https://gitcode.com/gh_mirrors/la/LANDrop 还在为不同设备间传输文件而烦恼吗&#xff1f;&#x1f914; LANDrop…...