题目描述
blablabla
算法1
BFS方式按层序列与反序列化
Golang 代码
/**
* Encodes a tree to a single string.
*/
func serialize(root *TreeNode) string {
ans := ""
if root == nil {
return "n"
}
// bfs方式序列化
q := list.New()
q.PushBack(root)
for q.Len()>0 {
e := q.Front()
t := e.Value.(*TreeNode)
if t == nil {
ans += "n "
} else {
ans += strconv.Itoa(t.Val)+" "
q.PushBack(t.Left)
q.PushBack(t.Right)
}
q.Remove(e)
}
return ans
}
/**
* Decodes your encoded data to tree.
*/
func deserialize(data string) *TreeNode {
nodes := strings.Split(data, " ")
if len(nodes) == 1{
return nil
}
nodes = nodes[:len(nodes)-1]
q := list.New()
root := new(TreeNode)
root.Val, _ = strconv.Atoi(nodes[0])
root.Left = nil
root.Right = nil
q.PushBack(root)
for i:=1; i<len(nodes);{
// 标记本层子节点区间[lower,upper)
lower := i
upper := i+2*q.Len()
for j:=lower;j<upper;{
// 依次建立子节点并入队
e := q.Front()
if nodes[j] == "n" {
e.Value.(*TreeNode).Left = nil
j++
}else {
p := new(TreeNode)
p.Val, _ = strconv.Atoi(nodes[j])
e.Value.(*TreeNode).Left = p
j++
q.PushBack(p)
}
if nodes[j] == "n" {
e.Value.(*TreeNode).Right = nil
j++
}else {
p := new(TreeNode)
p.Val, _ = strconv.Atoi(nodes[j])
e.Value.(*TreeNode).Right = p
j++
q.PushBack(p)
}
q.Remove(e)
}
i = upper
}
return root
}