二叉树的序列化和反序列化
洪笳淏 Lv4
 2021-10-02 17:19:00      

序列化的目的

  JSON 的运用非常广泛，比如我们经常将变成语言中的结构体序列化成 JSON 字符串，存入缓存或者通过网络发送给远端服务，消费者接受 JSON 字符串然后进行反序列化，就可以得到原始数据了。这就是「序列化」和「反序列化」的目的，以某种固定格式组织字符串，使得数据可以独立于编程语言。

问题描述

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

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

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

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：

avatar

1
2
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：

1
2
输入：root = []
输出：[]

示例 3：

1
2
输入：root = [1]
输出：[1]

示例 4：

1
2
输入：root = [1,2]
输出：[1,2]

提示：

  • 树中结点数在范围 [0, 104] 内
  • -1000 <= Node.val <= 1000

问题分析

  我们可以用 serialize 方法将二叉树序列化成字符串，用 deserialize 方法将序列化的字符串反序列化成二叉树，至于以什么格式序列化和反序列化，这个完全由你决定。比如说输入如下这样一棵二叉树：

avatar

  serialize 方法也许会把它序列化成字符串 2,1,#,6,3,#,#，其中 # 表示 null 指针，那么把这个字符串再输入 deserialize 方法，依然可以还原出这棵二叉树。也就是说，这两个方法会成对儿使用，你只要保证他俩能够自洽就行了。

  想象一下，二叉树结该是一个二维平面内的结构，而序列化出来的字符串是一个线性的一维结构。所谓的序列化不过就是把结构化的数据「打平」，其实就是在考察二叉树的遍历方式。

  二叉树的遍历方式有哪些？递归遍历方式有前序遍历，中序遍历，后序遍历；迭代方式一般是层级遍历。本文就把这些方式都尝试一遍，来实现 serialize 方法和 deserialize 方法。

结构体构造

1
2
3
4
5
6
7
8
9
10
11
12
type Codec struct {
    s       string
    null    string
    sep     string
}

func Constructor() Codec {
    return Codec{
        null    :   "#",  // 空节点
        sep     :   ",",  // 分隔符
    }
}

解题方法

前序遍历

  如下二叉树（# 代表空指针 null），可以直观看出前序遍历做的事情：

avatar

  那么 res = [1,2,-1,4,-1,-1,3,-1,-1]，这就是将二叉树「打平」到了一个列表中，其中 -1 代表 null。

那么，将二叉树打平到一个字符串中也是完全一样的，至此，我们已经可以写出序列化函数 serialize 的代码了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        this.s = this.s + this.null + this.sep
        return this.s
    }

    node := strconv.Itoa(root.Val)
    this.s = this.s + node + this.sep
    this.serialize(root.Left)
    this.serialize(root.Right)

    return this.s
}

  现在，思考一下如何写 deserialize 函数，将字符串反过来构造二叉树。首先我们可以把字符串转化成列表：

1
this.s = "1,2,#,4,#,#,3,#,#,"

  一般语境下，单单前序遍历结果是不能还原二叉树结构的，因为缺少空指针的信息，至少要得到前、中、后序遍历中的两种才能还原二叉树。但是这里的 node列表包含空指针的信息，所以只使用 node 列表就可以还原二叉树。那么，反序列化过程也是一样，先确定根节点 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
// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    m := make([]int,0) 
    j := 0
    f := 0
    x := 0

    for i:=0; i<len(data); i++ {
        if data[i] == ',' {
            continue
        } else if data[i] == '#' {	// 当前节点是空指针
            m = append(m,math.MinInt32)
        } else if data[i] == '-' {	// 当前节点是负值
            for j = i+1; data[j] != ','; j++ {
                x = int(data[j]) - '0'
                f = f*10+x
            }           
            m = append(m,-1*f)
            i = j
            f = 0 
        } else {
            for j = i; data[j] != ','; j++ {
                x = int(data[j]) - '0'
                f = f*10+x
            }
            
            m = append(m,f)
            i = j
            f = 0
        }
    }
    return helper(&m)
}

func helper(m *[]int) *TreeNode {
    if len(*m) == 0 {
        return nil
    }
    
    // 列表最左侧就是根节点
    first := (*m)[0]
    *m = (*m)[1:]	// 引用全局变量进行操作，就不会随递归栈进行变化

    if first == math.MinInt32 {
        return nil
    }
    
    root := &TreeNode{first,nil,nil}
    root.Left = helper(m)
    root.Right = helper(m)
    return root
}

后续遍历

  明白了前序遍历的解法，后序遍历就比较容易理解了，我们首先实现 serialize 序列化方法，只需要稍微修改辅助方法即可：

1
2
3
4
5
6
7
8
9
10
11
12
13
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        this.s = this.s + this.null + this.sep
        return this.s
    }

    this.serialize(root.Left)
    this.serialize(root.Right)

    x := strconv.Itoa(root.Val)
    this.s = this.s + x + this.sep
    return this.s
}

  后序遍历导致结果的顺序发生变化：

avatar

  关键的难点在于，如何实现后序遍历的 deserialize 方法呢？是不是也简单地将关键代码放到后序遍历的位置就行了呢？**deserialize 方法首先寻找 root 节点的值，然后递归计算左右子节点。那么我们这里也应该顺着这个基本思路走，后续遍历中，root 节点的值能不能找到？root 的值是列表的最后一个元素。我们应该从后往前取出列表元素，先用最后一个元素构造 root，然后递归调用生成 root 的左右子树。注意，根据上图，从后往前在 nodes 列表中取元素，一定要先构造 root.right 子树，后构造 root.left 子树**。

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
func (this *Codec) deserialize(data string) *TreeNode {
    if len(data) == 0 {
        return nil
    }

    m := make([]int,0)
    var(
        j = 0
        f = 0
        x = 0
    )

    for i:=0; i<len(data);i++ {
        if data[i] == ',' {
            continue
        } else if data[i] == '#' {
            m = append(m,math.MinInt32)
        } else if data[i] == '-' {
            for j=i+1; data[j] != ','; j++ {
                x = int(data[j]) - '0'
                f = f*10 + x
            }
            m = append(m,-1*f)
            f = 0
            i = j
        } else {
            for j=i; data[j] != ','; j++ {
                x = int(data[j]) - '0'
                f = f*10 + x
            }
            m = append(m,f)
            f = 0
            i = j
        }
    }

    return helper(&m)
}

func helper(m *[]int) *TreeNode {
    if len(*m) == 0 {
        return nil
    }

    n := len(*m)
    last := (*m)[n-1]
    *m = (*m)[:n-1]

    if last == math.MinInt32 {
        return nil
    }
    root := &TreeNode{
        Val     :       last,
        Left    :       nil,
        Right   :       nil,
    }
    root.Right = helper(m)	//一定要先构造 root.right 子树
    root.Left = helper(m)
    return root
}

中序遍历(不能实现)

  先说结论，中序遍历的方式行不通，因为无法实现反序列化方法 deserialize。

  序列化方法 serialize 依然容易，只要把字符串的拼接操作放到中序遍历的位置就行了。但是，我们刚才说了，要想实现反序列方法，首先要构造 root 节点。前序遍历得到的 nodes 列表中，第一个元素是 root 节点的值；后序遍历得到的 nodes 列表中，最后一个元素是 root 节点的值。

  而中序遍历的root 的值被夹在两棵子树的中间，也就是在 nodes 列表的中间，我们不知道确切的索引位置，所以无法找到 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
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        this.s = this.s + this.null + this.sep
        return this.s
    }

    q := []*TreeNode{root}
    nodeNum := 1
    for i:=0; nodeNum>0; i++ {
        p := []*TreeNode{}
        nodeNum = 0
        for j:=0; j<len(q); j++ {
            node := q[j]

            if node == nil {
                this.s = this.s + this.null + this.sep
                continue
            }
            
            this.s = this.s + strconv.Itoa(node.Val) + this.sep
            if node.Left != nil {
                nodeNum++
                p = append(p,node.Left)
            } else {
                p = append(p,nil)
            }

            if node.Right != nil {
                nodeNum++
                p = append(p,node.Right)
            } else {
                p = append(p,nil)
            }
        }
        q = p
    }
    return this.s
}

层级遍历序列化得出的结果如下图：

avatar

  可以看到，每一个非空节点都会对应两个子节点，那么反序列化的思路也是用队列进行层级遍历，同时用索引 i 记录对应子节点的位置：

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
func (this *Codec) deserialize(data string) *TreeNode {
    if len(data) == 0 {
        return nil
    }

    m := make([]int,0)
    var(
        j = 0
        f = 0
        x = 0
    )

    for i:=0; i<len(data);i++ {
        if data[i] == ',' {
            continue
        } else if data[i] == '#' {
            m = append(m,math.MinInt32)
        } else if data[i] == '-' {
            for j=i+1; data[j] != ','; j++ {
                x = int(data[j]) - '0'
                f = f*10 + x
            }
            m = append(m,-1*f)
            f = 0
            i = j
        } else {
            for j=i; data[j] != ','; j++ {
                x = int(data[j]) - '0'
                f = f*10 + x
            }
            m = append(m,f)
            f = 0
            i = j
        }
    }

    return helper(m)
}

func helper(m []int) *TreeNode {
    if len(m) == 0 || m[0] == math.MinInt32 {
        return nil
    }

    root := &TreeNode{m[0],nil,nil}
    q := []*TreeNode{root}
    for i:=1; i<len(m); {
        parent := q[0]
        q = q[1:]

        if m[i] != math.MinInt32 {	// 左子树
            parent.Left = &TreeNode{m[i],nil,nil}
            q = append(q,parent.Left)
        } else {
            parent.Left = nil
        }
        i++

        if m[i] != math.MinInt32 {	// 右子树
            parent.Right = &TreeNode{m[i],nil,nil}
            q = append(q,parent.Right)
        } else {
            parent.Right = nil
        }
        i++
    }
    return root
}
  • Post title：二叉树的序列化和反序列化
  • Post author：洪笳淏
  • Create time：2021-10-02 17:19:00
  • Post link：https://jiahaohong1997.github.io/2021/10/02/二叉树的序列化和反序列化/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments