题目描述

请实现两个函数，分别用来序列化和反序列化二叉树。

您需要确保二叉树可以序列化为字符串，并且可以将此字符串反序列化为原始树结构。

样例

你可以序列化如下的二叉树
    8
   / \
  12  2
     / \
    6   4

为："[8, 12, 2, null, null, 6, 4, null, null, null, null]"

golang 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
 /**
 * Encodes a tree to a single string.
 */

 func serialize(root *TreeNode) string {
    var ans = "["

    var queue []*TreeNode
    queue = append(queue,root)

    for len(queue) != 0 {
        myroot := queue[0]
        if myroot == nil {
            ans = ans + "null,"
        }else{
            ans = ans + strconv.Itoa(myroot.Val) + ","
            queue = append(queue,myroot.Left)
            queue = append(queue,myroot.Right)
        }
        queue = queue[1:]
    }
    ans = ans[:len(ans)-1] + "]"
    return ans
}





/**
 * Decodes your encoded data to tree.
 */
func deserialize(data string) *TreeNode {
    //对数据进行处理，分割成  []string
    data = data[1:len(data)-1]
    mydata := strings.Split(data,",")
    if mydata[0] == "null" {
        return nil
    }
    var root = new(TreeNode)
    root.Val,_ = strconv.Atoi(mydata[0])
    makeTree(mydata, root, 0)
    return root
}

//mydata为数据，root为根节点，num为root在mydata中的位置
func makeTree(mydata []string, root *TreeNode, num int) {
    //判断空节点数量
    var nilnum int
    for i := 0 ; i < num ; i++ {
        if mydata[i] == "null" {
            nilnum++
        }
    }
    //左子树存在
    if (num - nilnum) * 2 + 1 < len(mydata) {
        if mydata[(num - nilnum) * 2 + 1] != "null" {
            var left =  new(TreeNode)
            left.Val,_ = strconv.Atoi(mydata[(num - nilnum) * 2 + 1])
            root.Left = left
            makeTree(mydata, left , (num - nilnum) * 2 + 1)
        }
        //左子树为空   
    }
    //右子树存在
    if (num - nilnum + 1 ) * 2 < len(mydata) {
        if mydata[(num - nilnum + 1 ) * 2 ] != "null" {
            var right =  new(TreeNode)
            right.Val,_ = strconv.Atoi(mydata[(num - nilnum + 1 ) * 2 ])
            root.Right = right
            makeTree(mydata, right , (num - nilnum + 1 ) * 2 )
        }
        //右子树为空   
    }
}