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

序列化与反序列化

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

特点：

  • 可还原性。先序列化，再反序列化，所得结果与初始一致。
  • 配套性。因为序列化过程涉及分隔符的使用，所以一般针对某数据结构的序列化和反序列化算法是配套的。

LeetCode 原题链接
题目分析：
给出如下二叉树的数据结构定义：

  1. type TreeNode struct {
  2.     Val int
  3.     Left *TreeNode
  4.     Right *TreeNode
  5. }

给出一个根节点表示的二叉树，要求实现以下方法：

  • func (this Codec) serialize(root TreeNode) string，即把二叉树序列化为字符串。
  • func (this Codec) deserialize(data string) TreeNode，即把序列化得到的字符串反序列化为二叉树。

DFS 方法

序列化思路

序列化的过程中要插入一些分隔符（如逗号）以及用字符（如 # ）替代 nil 节点，这是为了方便反序列化。
利用深度优先搜索（DFS）的方法可以这么思考（假设采用前序遍历）：

  • 分：即拆分问题。序列化一棵二叉树，相当于根节点+ 序列化其左子树 + 序列化其右子树。
  • 治：序列化左 / 右子树是原问题的一个子问题。
  • 合： 根节点 + 左子树序列化结果 +右子树序列化结果

反序列化思路

首先根据刚才的分隔符把序列化得到的字符串分隔为字符串数组。
由于是采用前序遍历实现序列化，因此反序列化也要按照前序遍历的顺序进行。

  • 遇到 # 说明是一个 nil 节点。
  • 遇到非 # 说明是非 nil 节点，至少还有左右孩子，继续递归构建。

代码实现

type Codec struct {
    ser string
    deser []string
}

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)
}

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

func deserializeHelper(list *[]string) *TreeNode {  
    val, err := strconv.Atoi((*list)[0])
    *list = (*list)[1:]
    if err != nil {
        return nil
    }
    root := &TreeNode{Val: val}
    root.Left = deserializeHelper(list)
    root.Right = deserializeHelper(list)
    return root
}
/*
func deserializeHelper(list []string) *TreeNode {  
    val, err := strconv.Atoi(list[0])
    list = list[1:]
    if err != nil {
        return nil
    }
    root := &TreeNode{Val: val}
    root.Left = deserializeHelper(list)
    root.Right = deserializeHelper(list)
    return root
}
*/

非常值得注意的是：deserializeHelper 的参数是切片指针！如果不用，则会出错（如注释掉的同名方法那样）。
原因：因为递归涉及多层函数调用，若采用切片指针，则下一层的 *list = (*list)[1:] 的作用是全局的。而如果不用切片指针，list = list[1:] 的作用仅仅是当前层。

BFS 方法

序列化思路

用一个队列实现层次遍历，结果保存在 ser 中，初始根节点入队且添加到 ser：

  • 从队列中取出一个节点，若该节点非 nil，添加到 ser，同时将其左右节点入队（nil 也要入队）。
  • 若该节点为 nil，则添加 # 到 ser 中。

反序列化思路

用 ser 按层次遍历构树即可。

代码实现

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return ""
    }
    ser := []string{}
    queue := list.New()
    queue.PushBack(root)
    for queue.Len() > 0 {
        node := queue.Front().Value.(*TreeNode)
        queue.Remove(queue.Front())
        if node != nil {
            ser = append(ser, strconv.Itoa(node.Val))
            queue.PushBack(node.Left)
            queue.PushBack(node.Right)
        } else {
            ser = append(ser, "#")
        }

    }

    return strings.Join(ser, ",")
}   

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    if len(data) <= 0 { return nil }    

    temp := strings.Split(data, ",")
    val, _ := strconv.Atoi(temp[0])
    root := &TreeNode{Val: val, Left: nil, Right: nil}

    queue := list.New()
    queue.PushBack(root)
    i := 1
    for i < len(temp) {
        node := queue.Front().Value.(*TreeNode)
        queue.Remove(queue.Front())

        leftVal := temp[i]
        rightVal := temp[i+1]
        if leftVal != "#" {
            v, _ := strconv.Atoi(leftVal)
            leftNode := &TreeNode{Val: v, Left: nil, Right: nil}
            node.Left = leftNode
            queue.PushBack(leftNode)
        }
        if rightVal != "#" {
            v, _ := strconv.Atoi(rightVal)
            rightNode := &TreeNode{Val: v, Left: nil, Right: nil}
            node.Right = rightNode
            queue.PushBack(rightNode)
        }

        i += 2
    }

    return root   
}