37.md

序列化二叉树

题目

请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。

二叉树的序列化(Serialize)是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树等遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（#）

二叉树的反序列化(Deserialize)是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树

要求：序列化和反序列化都是空间复杂度 O(n)，时间复杂度 O(n)

思路

• 格式约定：空结点用[#]表示, 结点与结点用逗号[,]分隔
• 序列化 = 前序遍历 + 标记空节点
• 反序列化 = 怎么来的怎么回去

实现

import (
	"strconv"
	"strings"
)

func Serialize(root *TreeNode) string {
	if root == nil {
		return "#,"
	}

	str := strconv.Itoa(root.Val) + ","
	str += Serialize(root.Left)
	str += Serialize(root.Right)
	return str
}

func Deserialize(data string) *TreeNode {
	if len(data) == 0 {
		return nil
	}
	str := strings.Split(data, ",")
	index := -1
	var recur func(str []string) *TreeNode
	recur = func(str []string) *TreeNode {
		index++
		if index >= len(str) {
			return nil
		}
		if str[index] == "#" {
			return nil
		}
		value, _ := strconv.Atoi(str[index])
		node := &TreeNode{
			Val:   value,
			Left:  recur(str),
			Right: recur(str),
		}
		return node
	}
	root := recur(str)
	return root
}