Skip to main content

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

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

方法一：深度优先搜索

// d
func (Codec) serialize(root *TreeNode) string {
    sb := &strings.Builder{}     // 新建一个用 write 写入的 string
    var dfs func(*TreeNode)      // 这么写是为了嵌套的递归函数
    dfs = func(node *TreeNode) { // 前序的 dfs
        if node == nil {
            sb.WriteString("null,")
            return
        }
        sb.WriteString(strconv.Itoa(node.Val.(int)))
        sb.WriteByte(',')
        dfs(node.Left)
        dfs(node.Right)
    }
    dfs(root)
    return sb.String()
}

func (Codec) deserialize(data string) *TreeNode {
    sp := strings.Split(data, ",") // string 用 , 分割成 []string
    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()
}

学到了string的一些用法，详见注释。

这种方法构造的二叉树序列是123##456##这样子

方法二 括号表示编码 + 递归下降解码

T -> (T) num (T) | X

它的意义是：用 T 代表一棵树序列化之后的结果，| 表示 T 的构成为 (T) num (T) 或者 X，| 左边是对 T 的递归定义，右边规定了递归终止的边界条件。

因为：

  • T 的定义中，序列中的第一个字符要么是 X，要么是 (，所以这个定义是不含左递归的
  • 当我们开始解析一个字符串的时候，如果开头是 X，我们就知道这一定是解析一个「空树」的结构，如果开头是 (，我们就知道需要解析 (T) num (T) 的结构，因此这里两种开头和两种解析方法一一对应，可以确定这是一个无二义性的文法
  • 我们只需要通过开头的第一个字母是 X 还是 ( 来判断使用哪一种解析方法

所以这个文法是 LL(1) 型文法，如果你不知道什么是 LL(1) 型文法也没有关系，你只需要知道它定义了一种递归的方法来反序列化，也保证了这个方法的正确性——我们可以设计一个递归函数：

  • 这个递归函数传入两个参数，带解析的字符串和当前当解析的位置 ptr，ptr 之前的位置是已经解析的，ptr 和 ptr 后面的字符串是待解析的
  • 如果当前位置为 X 说明解析到了一棵空树，直接返回
  • 否则当前位置一定是 (，对括号内部按照 (T) num (T) 的模式解析
// 我自己写的代码
func (Codec) deserialize(data string) *TreeNode {
    // 省略结束条件
    leftRootValueStringKey := 0
    rightRootValueStringKey := 0
    // 省略...
    rootValueString := data[leftRootValueStringKey:rightRootValueStringKey]
    rootValue, _ := strconv.Atoi(rootValueString)
    // 这里拿到了 rootValue，以及左右子树的 data，然后就能递归了
    leftTreeData, rightTreeData := data[1:leftRootValueStringKey], data[rightRootValueStringKey:len(data)-1]
    return &TreeNode{rootValue, Constructor().deserialize(leftTreeData), Constructor().deserialize(rightTreeData)}
}
// leetcode 官方
func (Codec) deserialize(data string) *TreeNode {
    var parse func() *TreeNode
    // 先解析左子树，然后解析数字部分（nodeVal），最后解析右子树
    parse = func() *TreeNode {
        if data[0] == 'X' { // 如果为空则返回
            data = data[1:]
            return nil
        }
        node := &TreeNode{}
        data = data[1:] // 跳过左括号
        node.Left = parse()
        data = data[1:] // 跳过右括号
        i := 0
        for data[i] == '-' || '0' <= data[i] && data[i] <= '9' {
            i++
        }
        node.Val, _ = strconv.Atoi(data[:i])
        data = data[i:]
        data = data[1:] // 跳过左括号
        node.Right = parse()
        data = data[1:] // 跳过右括号
        return node
    }
    return parse()
}