mirror of
https://github.com/halfrost/LeetCode-Go.git
synced 2025-07-06 01:15:57 +08:00
113 lines
3.0 KiB
Markdown
113 lines
3.0 KiB
Markdown
# [297. Serialize and Deserialize Binary Tree](https://leetcode.com/problems/serialize-and-deserialize-binary-tree/)
|
||
|
||
|
||
## 题目
|
||
|
||
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.
|
||
|
||
Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.
|
||
|
||
**Clarification:** The input/output format is the same as [how LeetCode serializes a binary tree](https://leetcode.com/faq/#binary-tree). You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
|
||
|
||
**Example 1:**
|
||
|
||

|
||
|
||
```
|
||
Input: root = [1,2,3,null,null,4,5]
|
||
Output: [1,2,3,null,null,4,5]
|
||
```
|
||
|
||
**Example 2:**
|
||
|
||
```
|
||
Input: root = []
|
||
Output: []
|
||
```
|
||
|
||
**Example 3:**
|
||
|
||
```
|
||
Input: root = [1]
|
||
Output: [1]
|
||
```
|
||
|
||
**Example 4:**
|
||
|
||
```
|
||
Input: root = [1,2]
|
||
Output: [1,2]
|
||
```
|
||
|
||
**Constraints:**
|
||
|
||
- The number of nodes in the tree is in the range `[0, 104]`.
|
||
- `1000 <= Node.val <= 1000`
|
||
|
||
## 题目大意
|
||
|
||
设计一个算法,来序列化和反序列化二叉树。并不限制如何进行序列化和反序列化,但是你需要保证二叉树可以序列化为字符串,并且这个字符串可以被反序列化成原有的二叉树。
|
||
|
||
## 解题思路
|
||
|
||
- 1. 将给定的二叉树想象成一颗满二叉树(不存在的结点用 null 填充)。
|
||
- 2. 通过前序遍历,可以得到一个第一个结点为根的序列,然后递归进行序列化/反序列化即可。
|
||
|
||
## 代码
|
||
|
||
```go
|
||
package leetcode
|
||
|
||
import (
|
||
"strconv"
|
||
"strings"
|
||
|
||
"github.com/halfrost/LeetCode-Go/structures"
|
||
)
|
||
|
||
type TreeNode = structures.TreeNode
|
||
|
||
type Codec struct {
|
||
builder strings.Builder
|
||
input []string
|
||
}
|
||
|
||
func Constructor() Codec {
|
||
return Codec{}
|
||
}
|
||
|
||
// Serializes a tree to a single string.
|
||
func (this *Codec) serialize(root *TreeNode) string {
|
||
if root == nil {
|
||
this.builder.WriteString("#,")
|
||
return ""
|
||
}
|
||
this.builder.WriteString(strconv.Itoa(root.Val) + ",")
|
||
this.serialize(root.Left)
|
||
this.serialize(root.Right)
|
||
return this.builder.String()
|
||
}
|
||
|
||
// Deserializes your encoded data to tree.
|
||
func (this *Codec) deserialize(data string) *TreeNode {
|
||
if len(data) == 0 {
|
||
return nil
|
||
}
|
||
this.input = strings.Split(data, ",")
|
||
return this.deserializeHelper()
|
||
}
|
||
|
||
func (this *Codec) deserializeHelper() *TreeNode {
|
||
if this.input[0] == "#" {
|
||
this.input = this.input[1:]
|
||
return nil
|
||
}
|
||
val, _ := strconv.Atoi(this.input[0])
|
||
this.input = this.input[1:]
|
||
return &TreeNode{
|
||
Val: val,
|
||
Left: this.deserializeHelper(),
|
||
Right: this.deserializeHelper(),
|
||
}
|
||
}
|
||
``` |