Serialize and Deserialize Binary Tree

题目描述：

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000

思路:

用队列层次遍历一个二叉树变成string，再把string通过逗号分隔，再层次遍历成二叉树.

代码:

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

import "strconv"
type Codec struct {
     
}   


func Constructor() Codec {
    return Codec{}
}

// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
    var s string
    var queue []*TreeNode
   if root == nil {
       return s
   }
   queue = append(queue, root)
    for len(queue) != 0{
        node := queue[0]
        queue = queue[1:]
        if node == nil{
            s += ",null"
            continue
        }
        
        s += ","+strconv.Itoa(node.Val)
        if node.Left != nil{
            queue = append(queue, node.Left)
        }else{
            queue = append(queue, nil)
        }
        if node.Right != nil{
            queue = append(queue, node.Right)
        }else{
            queue = append(queue, nil)
        }
    }
   return s[1:]
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {    
    if data == ""{
        return nil
    }
    var queue []*TreeNode
    var datas []string = strings.Split(data,",")
    val,_ := strconv.Atoi(datas[0])
    root := &TreeNode{Val:val}
    
    queue = append(queue, root)
    index :=1
    for index<len(datas){
        node := queue[0]
        queue = queue[1:]
        left := datas[index]
        right := datas[index+1]
        if left[0] != 'n'{
            Left, _ := strconv.Atoi(left)
            node.Left = &TreeNode{Val:Left}
            queue = append(queue, node.Left)
        }else{
            node.Left = nil
        }
        if right[0] != 'n'{
            Right,_ := strconv.Atoi(right)
            node.Right = &TreeNode{Val:Right}
            queue = append(queue, node.Right)

        }else{
            node.Right = nil
        }
        index +=2
    }
    return root
}


/**
 * Your Codec object will be instantiated and called as such:
 * ser := Constructor();
 * deser := Constructor();
 * data := ser.serialize(root);
 * ans := deser.deserialize(data);
 */

代码效率：

执行用时：116 ms, 在所有 Go 提交中击败了9.89%的用户
内存消耗：10.8 MB, 在所有 Go 提交中击败了15.04%的用户