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

解法一：前序遍历
解法二：后序遍历
解法三：层序遍历

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

示例 1：
297.二叉树的序列化与反序列化 - 图1

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

树中结点数在范围 [0, 104] 内
-1000 <= Node.val <= 1000
解法一：前序遍历
```go /**
- 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 { var res string var dfs func(root TreeNode) dfs = func(root TreeNode) { if root == nil { res += “#,” return } res += fmt.Sprint(root.Val) + “,” dfs(root.Left) dfs(root.Right) } dfs(root) return res }

// Deserializes your encoded data to tree. func (this Codec) deserialize(data string) TreeNode { arr := strings.Split(data, “,”) var build func() TreeNode build = func() TreeNode { if len(arr) == 0 { return nil } var val string val, arr = arr[0], arr[1:] if val == “#” { return nil } head := new(TreeNode) head.Val, _ = strconv.Atoi(val) head.Left = build() head.Right = build() return head } return build() }

/**

Your Codec object will be instantiated and called as such:
ser := Constructor();
deser := Constructor();
data := ser.serialize(root);
ans := deser.deserialize(data); */ ```
解法二：后序遍历
推荐这种写法，条理清晰。 ```go /**
Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
} */ const SEP = “,” const NULL = “#”

type Codec struct { List []string }

func Constructor() Codec { return Codec{} }

// Serializes a tree to a single string. func (this Codec) serialize(root TreeNode) string { this.serializeList(root) return strings.Join(this.List, SEP) }

func (this Codec) serializeList(root TreeNode) { if root == nil { this.List = append(this.List, NULL) return } this.serializeList(root.Left) this.serializeList(root.Right) this.List = append(this.List, strconv.Itoa(root.Val)) }

// Deserializes your encoded data to tree. func (this Codec) deserialize(data string) TreeNode { this.List = []string{} for _, val := range strings.Split(data, SEP) { this.List = append(this.List, val) }

return this.deserializeList()

}

func (this Codec) deserializeList() TreeNode { if len(this.List) == 0 { return nil } var val string val, this.List = this.List[len(this.List)-1], this.List[:len(this.List)-1] if val == NULL { return nil } head := new(TreeNode) head.Val, _ = strconv.Atoi(val) head.Right = this.deserializeList() head.Left = this.deserializeList() return head }

/**

Your Codec object will be instantiated and called as such:
ser := Constructor();
deser := Constructor();
data := ser.serialize(root);
ans := deser.deserialize(data); */ ```
解法三：层序遍历
```go **
Definition for a binary tree node.
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
} */ const SEP = “,” const NULL = “#”

type Codec struct { List []string }

func Constructor() Codec { return Codec{} }

// Serializes a tree to a single string. func (this Codec) serialize(root TreeNode) string { queue := []TreeNode{} queue = append(queue, root) for len(queue) > 0 { var head TreeNode head, queue = queue[0], queue[1:] if head == nil { this.List = append(this.List, NULL) continue } this.List = append(this.List, strconv.Itoa(head.Val)) queue = append(queue, head.Left) queue = append(queue, head.Right) } return strings.Join(this.List, SEP) }

if len(this.List) == 0 {
    return nil
}
var val string
val = this.List[0]
if val == NULL {
    return nil
}
root := new(TreeNode)
root.Val, _ = strconv.Atoi(val)
queue := []*TreeNode{}
queue = append(queue, root)
for i := 0; len(queue) > 0; {
    var head *TreeNode
    head, queue = queue[0], queue[1:]
    i++
    left := this.List[i]
    if left != NULL {
        node := new(TreeNode)
        node.Val, _ = strconv.Atoi(left)
        head.Left = node
        queue = append(queue, head.Left)
    }
    i++
    right := this.List[i]
    if right != NULL {
        node := new(TreeNode)
        node.Val, _ = strconv.Atoi(right)
        head.Right = node
        queue = append(queue, head.Right)
    }

}
return root

}

/**

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

解法一：前序遍历

解法二：后序遍历

解法三：层序遍历