Leetcode - Serialize and Deserialize Binary Tree

https://leetcode.com/problems/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.

Example: 

You may serialize the following tree:

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]"

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

type Codec struct {
}

func Constructor() Codec {
    return Codec {
    } 
}

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

    return "[" + strings.Join(strs[0:i+1], ",") + "]"
}

// Deserializes your encoded data to tree.
func (this *Codec) deserialize(data string) *TreeNode {
    if data == "[]" {
        return nil
    }
    strs := strings.Split(data[1:len(data)-1], ",")
    // [1, 2, 3, null, null, 4, 5]
    
    val, _ := strconv.Atoi(strs[0])
    root := &TreeNode{Val: val}
    queue := []*TreeNode{root}
    i := 1
    
    for len(queue) > 0 {
        size := len(queue)
        for j := 0; j < size && i < len(strs); j++ {
            if strs[i] == "null" {
                queue[j].Left = nil
            } else {
                val, _ := strconv.Atoi(strs[i])
                queue[j].Left = &TreeNode{Val: val}
                queue = append(queue, queue[j].Left)
            }
            i++
            if i >= len(strs) {
                break
            }
            if strs[i] == "null" {
                queue[j].Right = nil
            } else {
                val, _ := strconv.Atoi(strs[i])
                queue[j].Right = &TreeNode{Val: val}
                queue = append(queue, queue[j].Right)
            }
            i++
        }
        queue = queue[size:]
    }
    return root
}


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

• 相关文章
• 全局相关文章