可视化图解算法36： 序列化二叉树-I（二叉树序列化与反序列化）

1. 题目

描述

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，可以根据前序遍历的方案序列化，如下图:

上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

保证 每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。

当然你也可以根据满二叉树结点位置的标号规律来序列化，还可以根据先序遍历和中序遍历的结果来序列化。不对序列化之后的字符串进行约束，所以欢迎各种奇思妙想。

数据范围：节点数 n≤100，树上每个节点的值满足 0≤val≤150

要求：序列化和反序列化都是空间复杂度 O(n)，时间复杂度 O(n)

示例1

输入：

{9,3,4,#,#,1,#,#,2,#,6,#,#}

返回值：

{9,3,4,#,#,1,#,#,2,#,6,#,#}

说明：

如题面图    

2. 解题思路

本题其实分为两部分，即将二叉树序列化为字符串、字符串再反序列化为二叉树。

先来看如何将二叉树序列化为字符串：

从输出结果来看，可以基于前序遍历的方式，即：先节点再左子树，最后右子树。

可以采用递归的形式完成，对应的递推公式如下：

再来看如何将字符串反序列化为二叉树：

对应的思路如下：

如果文字描述的不太清楚，你可以参考视频的详细讲解。

• Python版本：数据结构笔试面试算法-Python语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Python语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372247

• Java版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367355

• Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364780

3. 编码实现

核心代码如下：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** @param root TreeNode类* @return TreeNode类*/// Serialize 二叉树序列化为字符串
func Serialize(root *TreeNode) string {// write code here// 2. 递归终止条件if root == nil {return "#"}// 1. 问题分解（递推公式）return strconv.Itoa(root.Val) + "," + Serialize(root.Left) + "," + Serialize(root.Right)}// Deserialize 字符串反序列化为二叉树
func Deserialize(s string) *TreeNode {// write code herearr := strings.Split(s, ",") // 将字符串s切割成数组return recursion(arr)
}var index = -1func recursion(arr []string) *TreeNode {index++ //全局索引变量控制读取到的内容，索引每次加一// 2. 递归终止条件if index >= len(arr) {return nil //字符串中的内容已经取完}// 1. 问题分解（递推公式）var root *TreeNodeif arr[index] != "#" {// 1.1 创建节点v, _ := strconv.Atoi(arr[index])root = &TreeNode{Val: v}// 1.2 到左子树进行相似的处理root.Left = recursion(arr) //给节点的左子树赋值：递归左子树// 1.3 到右子树进行相似的处理root.Right = recursion(arr) //给节点的左子树赋值：递归右子树}// 1.4 返回节点return root
}

具体完整代码你可以参考下面视频的详细讲解。

• Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372247

• Java版本：数据结构笔试面试算法-Java语言版_哔哩哔哩_bilibili数据结构笔试面试算法-Java语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367355

• Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364780

4.小结

二叉树的序列化可以通过前序遍历的方法完成。二叉树的反序列化，首先将字符串转换为数组，再从数组中取出元素，在元素不为#的前提下，已当前元素的值创建节点，之后再用剩余的元素创建刚刚创建节点的左右子树（此过程通过递归的形式进行）。

《数据结构与算法》深度精讲课程正式上线啦！七大核心算法模块全解析：

      ✅ 链表

      ✅ 二叉树

      ✅ 二分查找、排序

      ✅ 堆、栈、队列

      ✅ 回溯算法

      ✅ 哈希算法

      ✅ 动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss897667807

• Java编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss161443488

• Golang编码实现：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ss63997

对于二叉树的相关算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：白日放歌须纵酒，青春作伴好还乡。