老卫带你学---leetcode刷题(297. 二叉树的序列化与反序列化)

297. 二叉树的序列化与反序列化

问题：

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
示例 2：
1
2
3

输入：root = []
输出：[]
示例 3：
1
2
3

输入：root = [1]
输出：[1]
示例 4：
1
2
3

输入：root = [1,2]
输出：[1,2]
1
2

解决

DFS完成序列化/反序列化

go

type TreeNode struct {
	Val int
	Left *TreeNode
	Right *TreeNode
}

type Codec struct {
	DataList []string
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	if root == nil{
		return "null"
	}
	return strconv.Itoa(root.Val)+","+this.serialize(root.Left)+","+this.serialize(root.Right)
}

func Constructor() Codec{
	return Codec{}
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	dataList := strings.Split(data,",")
	this.DataList = dataList
	return this.dfs()
}


func (this *Codec)dfs() *TreeNode{
	root := this.DataList[0]
	this.DataList = this.DataList[1:]
	if root == "null"{
		return nil
	}
	rootVal, _ := strconv.Atoi(root)
	t := &TreeNode{Val: rootVal}
	t.Left = this.dfs()
	t.Right = this.dfs()
	return t
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42