可视化图解算法37：序列化二叉树-II

1. 题目

描述

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

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

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

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

层序序列化(即用函数Serialize转化)如上的二叉树转为"{1,2,3,#,#,6,7}"，再能够调用反序列化(Deserialize)将"{1,2,3,#,#,6,7}"构造成如上的二叉树。

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

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

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

示例1

输入：

{1,2,3,#,#,6,7}

返回值：

{1,2,3,#,#,6,7}

说明：

如题面图    

示例2

输入：

{8,6,10,5,7,9,11}

返回值：

{8,6,10,5,7,9,11}

2. 解题思路

本题分为两部分，即二叉树的序列化与反序列化。上一篇文章《可视化图解算法36：序列化二叉树-I》讲解的是通过前序遍历的方法完成二叉树的序列化与反序列化，这一篇文章讲解通过层序遍历完成二叉树的序列化与反序列化。

先来看二叉树的序列化（将二叉树序列化为字符串）：

可以看出二叉树的节点值是通过层序遍历的方式转换为字符串的（空节点字符串为#），对于层序遍历可以通过队列来辅助完成（二叉树层序遍历详细内容参考：《可视化图解算法23：二叉树的层序遍历》）。具体思路为：

1. 创建队列，根节点入队列；

2. 节点出队列，出队列的节点值构成字符串，再将左右子树入队列；

   注：左右子树有可能为null，也需要入队列。

3. 左右子树出队列，出队列的节点值构成字符串的字符，再将出队列节点的左右子树入队列，如此循环往复。

再来看二叉树的反序列化（将字符串转换为二叉树）：

二叉树序列化的时候是通过层序遍历的方法，反序列化的时候需要与此相对应（即也需要通过层序遍历的思想完成）。具体思路为：

1. 以逗号对字符串进行分割，将其转换为数组；

2. 基于层序遍历的形式将数组中的字符串转为二叉树的节点并形成二叉树：

   节点出队列，根据数组中的值创建左子树（如果当前值是#，不创建左子树），创建的左子树再入队列；根据数组中的值创建右子树（如果当前值是#，不创建左子树），创建的右子树再入队列；

3. 依次循环，直至数组中的元素取完。

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

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

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

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

3. 编码实现

核心代码如下：

type TreeNode struct {Val   intLeft  *TreeNodeRight *TreeNode
}/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** @param root TreeNode类* @return TreeNode类*/
// Serialize 二叉树序列化为字符串
func Serialize(root *TreeNode) string {// write code hereif root == nil {return "#"}// 1. 创建队列并赋值queue := []*TreeNode{root}res := ""// 2. 操作队列（二叉树节点出队列，左右子树入队列）for len(queue) > 0 {// 2.1 节点出队列node := queue[0]queue = queue[1:]if node == nil { //null节点没有叶子节点，不需要操作res += "#" + ","continue}res += strconv.Itoa(node.Val) + ","//2.2 左子树入队列queue = append(queue, node.Left)//2.3 右子树入队列queue = append(queue, node.Right)}res = strings.TrimRight(res[:len(res)-1], ",#") //去掉末尾连续的" ,# "return res
}// Deserialize 字符串反序列化为二叉树
func Deserialize(s string) *TreeNode {// write code hereif s == "#" || strings.TrimSpace(s) == "" {return nil}// 1. 分割（序列化的）字符串arr := strings.Split(s, ",")// 2. 创建root节点rootVal, _ := strconv.Atoi(arr[0])root := &TreeNode{Val: rootVal}// 3. 操作队列（二叉树节点出队列，左右子树入队列）queue := []*TreeNode{root}index := 1 // arr对应的索引for index < len(arr) {// 3.1 节点出队列node := queue[0]  // 队列的头节点queue = queue[1:] // 删除队列的头节点// 3.2 创建左子树并入队列if arr[index] != "#" {leftVal, _ := strconv.Atoi(arr[index])node.Left = &TreeNode{Val: leftVal}queue = append(queue, node.Left) //添加左子树到队列}index++ // 移动索引（不管左子树用到了#还是数值，都需要移动index）// 3.3 创建右子树并入队列if index < len(arr) && arr[index] != "#" {rightVal, _ := strconv.Atoi(arr[index])node.Right = &TreeNode{Val: rightVal}queue = append(queue, node.Right) // 添加右子树到队列}index++ // 移动索引的值（不管右子树用到了#还是数值，都需要移动index）}return root
}

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

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

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

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

4.小结

二叉树的序列化与反序列化可以通过层序遍历的方法来完成，层序遍历可以通过队列来辅助完成。

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

        ✅   链表

        ✅   二叉树

        ✅   二分查找、排序

        ✅   堆、栈、队列

        ✅   回溯算法

        ✅   哈希算法

        ✅   动态规划

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

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

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

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

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

今日佳句：百川东到海，何时复西归？