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

1. 题目描述

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

2. 思路

1. 思路一
   • 层序遍历
   • 序列化：节点是 null，将符号 ‘X’ 推入 res 数组；节点是数值，将节点值推入数组 res，并将它的左右子节点入列
   • 反序列化：按层序队列依次取父节点，并用 index 顺序读取它的左、右子节点；不能直接用 i、i+1、i+2 作为固定坐标关系
2. 思路二：类似从前序与中序遍历序列构造二叉树.md，但是是错误的的

3. 实现

3.1. 层序遍历

/**
 * 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 {
	queue := make([]*TreeNode, 0)
	queue = append(queue, root)
	res := make([]string, 0)
	for len(queue) > 0 {
		n := queue[0]
		queue = queue[1:]

		if n != nil {
			res = append(res, strconv.Itoa(n.Val))
			queue = append(queue, n.Left)
			queue = append(queue, n.Right)
		} else {
			res = append(res, "X")
		}
	}

	return strings.Join(res, ",")
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
	if data == "X" {
		return nil
	}
	list := strings.Split(data, ",")
	rootVal, _ := strconv.Atoi(list[0])
	root := &TreeNode{Val: rootVal}
	queue := []*TreeNode{root}
	index := 1

	for index < len(list) {
		node := queue[0]
		queue = queue[1:]
		leftVal := list[index]
		rightVal := list[index+1]
		if leftVal != "X" {
			v, _ := strconv.Atoi(leftVal)
			leftNode := &TreeNode{Val: v}
			node.Left = leftNode
			queue = append(queue, leftNode)
		}
		if rightVal != "X" {
			v, _ := strconv.Atoi(rightVal)
			rightNode := &TreeNode{Val: v}
			node.Right = rightNode
			queue = append(queue, rightNode)
		}
		index += 2
	}
	return root

}

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

3.2. 前序+中序（错误）

type Codec struct {
}

func Constructor() Codec {
	return Codec{
	}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
	preorder := make([]string, 0)
	preOrder(root, &preorder)

	inorder := make([]string, 0, len(preorder))
	inOrder(root, &inorder)

	if len(preorder) == 0 {
		return ""
	}

	pre := strings.Join(preorder, ":")
	mid := strings.Join(inorder, ":")
	return pre + "_" + mid
}

func inOrder(root *TreeNode, vals *[]string) {
	if root == nil {
		return
	}

	inOrder(root.Left, vals)
	*vals = append(*vals, strconv.Itoa(root.Val))
	inOrder(root.Right, vals)
}

func preOrder(root *TreeNode, vals *[]string) {
	if root == nil {
		return
	}

	*vals = append(*vals, strconv.Itoa(root.Val))
	preOrder(root.Left, vals)
	preOrder(root.Right, vals)
}

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

	split := strings.Split(data, "_")
	preorder := make([]int, 0)
	pre := strings.Split(split[0], ":")
	for _, v := range pre {
		num, _ := strconv.Atoi(v)
		preorder = append(preorder, num)
	}
	inorder := make([]int, 0)
	mid := strings.Split(split[1], ":")
	for _, v := range mid {
		num, _ := strconv.Atoi(v)
		inorder = append(inorder, num)
	}

	return buildTree(preorder, inorder)
}

func buildTree(preorder []int, inorder []int) *TreeNode {
	if len(preorder) == 0 || len(inorder) == 0 { return nil }
	rootVal := preorder[0]
	idx := find(inorder, rootVal)
	root := &TreeNode{Val: rootVal}
	root.Left = buildTree(preorder[1:idx+1], inorder[:idx])
	root.Right = buildTree(preorder[idx+1:], inorder[idx+1:])
	return root
}

func find(nums []int, target int) int {
	for i, num := range nums {
		if num == target { return i }
	}
	return -1
}

4. 参考

• 『手画图解』剖析DFS、BFS解法 | 二叉树的序列化与反序列化 - 二叉树的序列化与反序列化 - 力扣（LeetCode）