# 题目链接
# 题目描述
请实现两个函数，分别用来序列化和反序列化二叉树。
# 解题思路
序列化：二叉树的层次遍历，子树为Null的情况也需要加上 反序列化：切割序列化后的字符串，利用队列辅助，层次遍历构造回原始二叉树
func serialize(root *TreeNode) string {
ans := "["
// 中序遍历
nodeQueue := make([]*TreeNode,0)
nodeQueue = append(nodeQueue,root) // 添加根元素
for len(nodeQueue) != 0 {
tmpNode := nodeQueue[0]
nodeQueue = nodeQueue[1:]
if tmpNode == nil {
ans += "null" + ","
continue // null无需无差别添加子节点
} else {
ans += strconv.Itoa(tmpNode.Val) + ","
}
nodeQueue = append(nodeQueue,tmpNode.Left)
nodeQueue = append(nodeQueue,tmpNode.Right)
}
ans = ans[:len(ans)-1] // 去掉最后一个","
return ans + "]"
}
func deserialize(data string) *TreeNode {
data = data[1:len(data)-1] // 去除[]
dataSplit := strings.Split(data,",") // 切割
if len(dataSplit) == 1 { // 按照序列化规则，如果根节点有内容，至少切出三个元素
return nil
}
nodeQueue := make([]*TreeNode,0)
dataSplitCount := 0
rootVal,_ := strconv.Atoi(dataSplit[dataSplitCount]) // Itoa 不会出错，Atoi可能会出错，所以有error
root := &TreeNode{Val: rootVal,Left: nil,Right: nil}
dataSplitCount++
nodeQueue = append(nodeQueue,root) // 添加首元素
for len(nodeQueue) != 0 {
tmpNode := nodeQueue[0]
nodeQueue = nodeQueue[1:]
leftNodeContext := dataSplit[dataSplitCount] // 添加左节点
dataSplitCount++
if leftNodeContext == "null" {
tmpNode.Left = nil
} else {
leftVal,_ := strconv.Atoi(leftNodeContext)
leftNode := &TreeNode{Val: leftVal,Left: nil,Right: nil}
tmpNode.Left = leftNode
nodeQueue = append(nodeQueue,leftNode)
}
rightNodeContext := dataSplit[dataSplitCount]
dataSplitCount++
if rightNodeContext == "null" {
tmpNode.Right = nil
} else {
rightVal,_ := strconv.Atoi(rightNodeContext)
rightNode := &TreeNode{Val: rightVal,Left: nil,Right: nil}
tmpNode.Right = rightNode
nodeQueue = append(nodeQueue,rightNode)
}
}
return root
}
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69