剑指 Offer 37. 序列化二叉树（golang版）

• 题目描述

• 思路
  1、借助前序遍历的思想，进行序列化和反序列化
  2、序列化较简单，前序遍历，将节点值追加到指针字符串中，注意为空节点代替字符为“#”和分隔符“,”
  3、反序列化也是前序遍历思想，注意下标值K为*int类型，递归返回条件为下标值K小于切片字符串长度或节点值为“#”

• 代码

func Serialize( root *TreeNode ) *TreeNode {
	var str string
	serialize(root, &str)
	return deSerialize(str)
}
//序列化,“#”代表空节点，“,”代表分隔符
func serialize(root *TreeNode, str *string){
	//前序遍历，如果为空节点，则追加“#,”
	if root == nil {
		*str += "#,"
		return
	}
	//若节点不为空则追加节点值和“,”
	*str += strconv.Itoa(root.Val)
	*str += ","
	//处理左子树
	serialize(root.Left, str)
	//处理右子树
	serialize(root.Right, str)
}
//反序列化前准备
func deSerialize(str string) *TreeNode{
	//将字符串以“,”分隔，返回[]string类型
	strSlice := strings.Split(str,",")
	//处理序列化时字符串末尾多的“,”
	strSlice1 := strSlice[:len(strSlice)-1]
	//k是切片的下标值，传引用
	var k = 0
	root := de(&strSlice1,&k)
	return root
}
//反序列化
func de(str *[]string, k *int) *TreeNode{
	//构建当前节点

	//若下标值大约切片长度则说明已经遍历完毕，返回
	if *k >= len(*str){
		return nil
	}
	//若为“#”说明当前节点为空节点
	if (*str)[*k] == "#" {
		return nil
	}
	root := &TreeNode{}
	val,_ := strconv.Atoi((*str)[*k])

	root.Val = val
	//处理左右子树
	*k++
	root.Left = de(str,  k)
	*k++
	root.Right = de(str, k)
	return root
}

• 测试代码

package main

import (
	"strconv"
	"strings"
)

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

func Serialize( root *TreeNode ) *TreeNode {
	var str string
	serialize(root, &str)
	return deSerialize(str)
}
//序列化,“#”代表空节点，“,”代表分隔符
func serialize(root *TreeNode, str *string){
	//前序遍历，如果为空节点，则追加“#,”
	if root == nil {
		*str += "#,"
		return
	}
	//若节点不为空则追加节点值和“,”
	*str += strconv.Itoa(root.Val)
	*str += ","
	//处理左子树
	serialize(root.Left, str)
	//处理右子树
	serialize(root.Right, str)
}
//反序列化前准备
func deSerialize(str string) *TreeNode{
	//将字符串以“,”分隔，返回[]string类型
	strSlice := strings.Split(str,",")
	//处理序列化时字符串末尾多的“,”
	strSlice1 := strSlice[:len(strSlice)-1]
	//k是切片的下标值，传引用
	var k = 0
	root := de(&strSlice1,&k)
	return root
}
//反序列化
func de(str *[]string, k *int) *TreeNode{
	//构建当前节点

	//若下标值大约切片长度则说明已经遍历完毕，返回
	if *k >= len(*str){
		return nil
	}
	//若为“#”说明当前节点为空节点
	if (*str)[*k] == "#" {
		return nil
	}
	root := &TreeNode{}
	val,_ := strconv.Atoi((*str)[*k])

	root.Val = val
	//处理左右子树
	*k++
	root.Left = de(str,  k)
	*k++
	root.Right = de(str, k)
	return root
}


func main(){
	root := &TreeNode{4, nil, nil}
	node1 := &TreeNode{2, nil, nil}
	node2 := &TreeNode{5, nil, nil}
	node3 := &TreeNode{1, nil, nil}
	node4 := &TreeNode{3, nil, nil}

	root.Left = node1
	root.Right = node2
	node1.Left = node3
	node1.Right = node4

	Serialize(root)

}

LeetCode该题不能用go语言去解，服气。。