题目描述

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

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

示例:

你可以将以下二叉树：

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

算法

其实这道题使用深度优先遍历和宽度优先遍历都可以，只要保证了二叉树的结构信息就可以了，而我采用的就是宽度优先遍历，而我第一次提交超时的原因是保存二叉树结构信息的时候，多保存了一下空的结点信息，例如对于如下二叉树

         1
       /  \
    2       3
   / \      / \
 nil nil   4   5
 /     \        \
 nil     nil     6

null

序列化方式：

采用层序遍历的方式，一层一层的读取结点：

nullnil

序列化方式：

,
nil

代码

// TreeNode ...
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// Codec ...
type Codec struct {
}

// Constructor ...
func Constructor() Codec {
	return Codec{}
}

func (c *Codec) serizalize(root *TreeNode) string {
	// 也就是二叉树的层序遍历，因为只有这样才能保存二叉树的结构信息
	if root == nil {
		return "null,"
	}
	res := ""
	que := []*TreeNode{root}
	for {
		tmpQue := []*TreeNode{}
		for _, nodeV := range que {
			if nodeV == nil {
				res += "null,"
			} else {
				value := strconv.Itoa(nodeV.Val)
				res = res + value + ","
				if nodeV.Left != nil {
					tmpQue = append(tmpQue, nodeV.Left)
				} else {
					tmpQue = append(tmpQue, nil)
				}
				if nodeV.Right != nil {
					tmpQue = append(tmpQue, nodeV.Right)
				} else {
					tmpQue = append(tmpQue, nil)
				}
			}
		}
		nilFlag := false
		for _, nodeT := range tmpQue {
			if nodeT != nil {
				nilFlag = true
				break
			}
		}
		if !nilFlag {
			break
		}
		que = tmpQue
	}
	return res
}

func (c *Codec) deserialize(data string) *TreeNode {
	nodeVs := strings.Split(data, ",")
	nodeVs = nodeVs[:len(nodeVs)-1]
	if len(nodeVs) == 0 {
		return nil
	}
	if nodeVs[0] == "null" {
		return nil
	}
	rootVal, _ := strconv.Atoi(nodeVs[0])
	root := &TreeNode{
		Val: rootVal,
	}
	count := 1
	que := []*TreeNode{root}
	if count == len(nodeVs) {
		return root
	}
	for {
		tmpQue := []*TreeNode{}
		for _, tmpNode := range que {
			if tmpNode == nil {
				continue
			}
			// 每个结点有左右两个孩子
			for i := 0; i < 2; i++ {
				var node *TreeNode
				if nodeVs[count] != "null" {
					nodeV, _ := strconv.Atoi(nodeVs[count])
					node = &TreeNode{Val: nodeV}
				}
				if i == 0 {
					tmpNode.Left = node
				} else {
					tmpNode.Right = node
				}
				tmpQue = append(tmpQue, node)
				if count++; count == len(nodeVs) {
					return root
				}
			}
		}
		que = tmpQue
	}
}