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, 10⁴] 内
• -1000 <= Node.val <= 1000

题解

使用先序遍历，在遍历树节点时将树结构系列化成字符串，使用 # 表示空节点。
在反序列化时，也是先序遍历将字符还原成树结构，此时需要注意的是，递归操作的字符串地址要相同，最后反序列化出来的树结构才能保证正确。

代码实现

/**
 * 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 {
	// 先序遍历序列化
	res := preorderSerialize(root)
	return strings.Join(res, ",")
}

func preorderSerialize(root *TreeNode) (res []string) {
	if root == nil {
		return nil
	}
	var preorder func(node *TreeNode)
	preorder = func(node *TreeNode) {
		if node == nil {
			res = append(res, "#")
			return
		}
		res = append(res, fmt.Sprintf("%d", node.Val))
		preorder(node.Left)
		preorder(node.Right)
		return
	}
	preorder(root)
	return
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if data == "" {
		return nil
	}
	s := strings.Split(data, ",")
	var build func() *TreeNode
	build = func() *TreeNode {
		if s[0] == "#" {
			s = s[1:]
			return nil
		}
		val, _ := strconv.Atoi(s[0])
		root := &TreeNode{
			Val: val,
		}
		s = s[1:] // left 和 right 递归共用此数组
		root.Left = build()
		root.Right = build()
		return root
	}
	return build()
}

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