[Leetcode]41.序列化和反序列化二叉搜索树
序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。
示例 1：
输入：root = [2,1,3]
输出：[2,1,3]
示例 2：
输入：root = []
输出：[]
提示：
树中节点数范围是 [0, 104]
0 <= Node.val <= 104
题目数据 保证 输入的树是一棵二叉搜索树。
思想一：BFS层序遍历序列化，空的节点使用空“”代替
同样BFS反序列化，遇到空“”注意将其转化为空结点
type Codec struct { }func Constructor() Codec { return Codec{} }
// Serializes a tree to a single string. func (this *Codec) serialize(root *TreeNode) string { if root ==nil{ return "" } var res []string var s []*TreeNode s = append(s,root) for len(s)>0{ var temp []*TreeNode for _,n :=range s{ if n!=nil{ res = append(res,strconv.Itoa(n.Val)) temp = append(temp,n.Left) temp = append(temp,n.Right) }else{ res = append(res,"") } } s = temp temp = temp[0:0] } return strings.Join(res, ",") }
// Deserializes your encoded data to tree. func (this *Codec) deserialize(data string) *TreeNode { if len(data)==0{ return nil } var res = strings.Split(data, ",") var root = &TreeNode{} root.Val, _ = strconv.Atoi(res[0]) var queue = []*TreeNode{root} res = res[1:]
for 0 < len(queue){ if res[0]!=""{ l,_ :=strconv.Atoi(res[0]) queue[0].Left = &TreeNode{Val:l} queue = append(queue,queue[0].Left) } if res[1]!=""{ r,_ :=strconv.Atoi(res[1]) queue[0].Right = &TreeNode{Val:r} queue = append(queue,queue[0].Right) } queue = queue[1:] res = res[2:] } return root }
思想二：用DFS遍历
type Codec struct {
}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
if root == nil{
return ""
}
return strconv.Itoa(root.Val)+","+this.serialize(root.Left)+","+this.serialize(root.Right)
}
func dfs4(data *[]string) *TreeNode{
cur :=(*data)[0]
*data = (*data)[1:]
if cur ==""{
return nil
}else{
val ,_:=strconv.Atoi(cur)
node := &TreeNode{
Val: val,
Left: dfs4(data),
Right: dfs4(data),
}
return node
}
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
str := strings.Split(data,",")
return dfs4(&str)
}
链接：https://leetcode-cn.com/problems/serialize-and-deserialize-bst