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

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

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
编码的字符串应尽可能紧凑。

思路：通法，就是序列化转化，再反序列化回来，递归左右子树

//dfs 前序遍历
type Codec struct {
    res []string
}
func Constructor() Codec {
    return Codec{}
}
// 序列化树 为单个字符串。
func (this *Codec) serialize(root *TreeNode) string {
    if root == nil {
        return "#"              //nil节点用# 占位
    }
    return strconv.Itoa(root.Val) + "," + this.serialize(root.Left) + "," + this.serialize(root.Right)          //格式转化，数字转化为ACill码，用逗号分隔
}
// 反序列化编码数据 为树。
func (this *Codec) deserialize(data string) *TreeNode {
    this.res = strings.Split(data, ",")     //以逗号切割，分成几个小部分字符串
    return this.dfsDeserialize()            //递归1
}
func (this *Codec) dfsDeserialize() *TreeNode {
    node := this.res[0]                 //递归3
    this.res = this.res[1:]
    if node == "#" {
        return nil
    }
    v, _ := strconv.Atoi(node)      //字符串转换为 int类型
    root := &TreeNode{
        Val:   v,
        Left:  this.dfsDeserialize(),       //递归2
        Right: this.dfsDeserialize(),
    }
    return root
}

//bfs解法
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 ""
    }

    var res []string
    var queue = []*TreeNode{root}

    for 0 < len(queue) {
        if queue[0] != nil {
            res = append(res, strconv.Itoa(queue[0].Val))
            queue = append(queue, queue[0].Left, queue[0].Right)

        } else {
            res = append(res, "#")
        }
        queue = queue[1:]
    }
    return strings.Join(res, ",")
}

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

    var res = strings.Split(data, ",")
    var root = &TreeNode{}
    root.Val, _ = strconv.Atoi(res[0])

    var queue = []*TreeNode{root}
    res = res[1:]

    for 0 < len(queue) {
        if res[0] != "#" {
            l, _ := strconv.Atoi(res[0])
            queue[0].Left = &TreeNode{Val: l}
            queue = append(queue, queue[0].Left)
        }

        if res[1] != "#" {
            r, _ := strconv.Atoi(res[1])
            queue[0].Right = &TreeNode{Val: r}
            queue = append(queue, queue[0].Right)
        }
        queue = queue[1:]
        res = res[2:]
    }
    return root
}