二叉树的序列化和反序列化

剑指 Offer II 048. 序列化与反序列化二叉树 - 力扣（Leetcode）

介绍

一道经典的序列化题目，题目给的是二叉树的结构，我们需要将二叉树的结构转换为字符串，再转换回去
基本思路是使用前序遍历，把结果以字符串形式存储起来。(存储结构很重要)

第一版的算法为

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {
}

func Constructor() (_ Codec) {
    return 
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root==nil {return ""}
    k :=root
    s:=""
    s+=string(k.Val)
    s+=dfs(k.Left)
    s+=dfs(k.Right)
    return s
}
func dfs(root *TreeNode) string{
    if root==nil{return "#"}
    s:=""
    k:=root
    s+=string(k.Val)
    s+=dfs(k.Left)
    s+=dfs(k.Right)
    return s
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {    
    if data=="" {return nil}
    root:=&TreeNode{0,nil,nil}
    var num *int 
    k:=0
    num = &k
    s:=data[*num]
    if s=='#'{ return nil}
    root.Val=int(s)
    root.Left=sdfs(data,num)
    root.Right=sdfs(data,num)
    return root
}
func sdfs(data string,num *int) *TreeNode{
    *num+=1
    if *num>=len(data){return nil}
    root:=&TreeNode{0,nil,nil}
    s:=data[*num]
    if s=='#'{return nil}
    root.Val=int(s)
    root.Left=sdfs(data,num)
    root.Right=sdfs(data,num)
    return root
}

/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */

交上去发现错了，错误案例为

[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]

思考了一下为什么，我这里存储是把null和数字都当成一个字符存进去，即存成4-7-3##等等，使得我每次读数的时候只能读一个字符，所以遇到负数则会出现问题。

那么代码可以改为在字符串中添加 ‘,’，然后用split()方法来抽离。

修改后的代码为

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {}

func Constructor() (_ Codec) {
    return 
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root==nil {return ""}
    k :=root
    s:=""
    s+=strconv.Itoa(k.Val)
    s+=dfs(k.Left)
    s+=dfs(k.Right)
    return s
}
func dfs(root *TreeNode) string{
    if root==nil{return ",#"}
    s:=""
    k:=root
    s+=","+strconv.Itoa(k.Val)
    s+=dfs(k.Left)
    s+=dfs(k.Right)
    return s
}
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {    
    if data=="" {return nil}
    root:=&TreeNode{0,nil,nil}
    var num *int 
    k:=0
    num = &k
    h:=strings.Split(data,",")
    s:=h[*num]
    if s=="#"{ return nil}
    root.Val,_=strconv.Atoi(s)
    root.Left=sdfs(data,num,h)
    root.Right=sdfs(data,num,h)
    return root
}
func sdfs(data string,num *int,h []string) *TreeNode{
    *num+=1
    root:=&TreeNode{0,nil,nil}
    if *num>=len(h){return nil}
    s:=h[*num]
    if s=="#"{return nil}
    root.Val,_=strconv.Atoi(s)
    root.Left=sdfs(data,num,h)
    root.Right=sdfs(data,num,h)
    return root
}

/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */

答案过了，那么这个代码的问题有哪些

• 位于全局的多余的dfs和sdfs
• 代码的长度，耦合度高
• 运行速度较慢(击败“47%”)
• 多余的空间复杂度

那么我们就可以根据以上方法进行优化，拼接字符串也可以使用strings来实现

官方解：

type Codec struct{}

func Constructor() (_ Codec) {
    return
}

func (Codec) serialize(root *TreeNode) string {
    sb := &strings.Builder{}
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {
            sb.WriteString("null,")
            return
        }
        sb.WriteString(strconv.Itoa(node.Val))
        sb.WriteString(",")
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return sb.String()
}

func (Codec) deserialize(data string) *TreeNode {
    sp := strings.Split(data, ",")
    var build func() *TreeNode
    build = func() *TreeNode {
        if sp[0] == "null" {
            sp = sp[1:]
            return nil
        }
        val, _ := strconv.Atoi(sp[0])
        sp = sp[1:]
        return &TreeNode{val, build(), build()}
    }
    return build()
}

终解

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type Codec struct {
    
}

func Constructor() (_ Codec) {
    return
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    sb :=  &strings.Builder{}
    var dfs func(*TreeNode)
    dfs =func(root *TreeNode){
        if root==nil{
            sb.WriteString("null,")
            return
        }
        sb.WriteString(strconv.Itoa(root.Val))
        sb.WriteString(",")
        dfs(root.Left)
        dfs(root.Right)
    }
    dfs(root)
    return sb.String()
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {    
    s := strings.Split(data, ",")
	var dfs func() *TreeNode
	dfs = func() *TreeNode {
		if s[0] == "null" {
			s = s[1:]
			return nil
		}
		node := &TreeNode{0, nil, nil}
		val, _ := strconv.Atoi(s[0])
		node.Val = val
		s = s[1:]
		node.Left = dfs()
		node.Right = dfs()
		return node
	}
	return dfs()
}


/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */

Q.E.D.