449. 序列化和反序列化二叉搜索树

题目描述

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。对序列化 / 反序列化算法的工作方式没有限制。您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

示例 1：

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

示例 2：

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

提示：

树中节点数范围是 [0, 10⁴]
0 <= Node.val <= 10⁴
题目数据保证输入的树是一棵二叉搜索树。

解法一：前序遍历

 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


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

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 "-"
    }
    ret := fmt.Sprintf("%d", root.Val)
    left, right := this.serialize(root.Left), this.serialize(root.Right)
    ret += fmt.Sprintf(",%s,%s", left, right)
    return ret
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    path := strings.Split(data, ",")
    i := 0
    var buildTree func() *TreeNode
    buildTree = func() *TreeNode {
        num, err := strconv.Atoi(path[i])
        i++
        if err != nil {
            return nil
        }
        root := &TreeNode{Val: num}
        root.Left = buildTree()
        root.Right = buildTree()
        return root
    }
    return buildTree()
}

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