2022-01-25: serialize and deserialize n-ary tree. Serialization means that a

2022-01-25： Serialization and deserialization N Fork tree .

Serialization is the process of converting a data structure into a sequence of bits , So you can store it in a file or in a memory buffer , So that the structure can be restored later in the same or different computer environment .

Design a serialization and deserialization N Fork tree algorithm .

One N A fork tree means that each node has no more than N A rooted tree with child nodes .

serialize / There are no restrictions on the algorithm implementation of deserialization algorithm .

You just need to guarantee N The fork tree can be serialized into a string and the string can be deserialized into the original tree structure .

Be careful ：

N The scope of 1, 1000

Don't use class members / Global variables / Static variables to store state .

Your serialization and deserialization algorithms should be stateless .

Power button 428.

answer 2022-01-25：

Natural intelligence . recursive .

The code to use golang To write . The code is as follows ：

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func main() {
    a := NewNode2(1)
    b := NewNode2(2)
    c := NewNode2(3)
    d := NewNode2(4)
    e := NewNode2(5)
    f := NewNode2(6)
    g := NewNode2(7)
    a.children = append(a.children, b)
    a.children = append(a.children, c)
    a.children = append(a.children, d)
    b.children = append(b.children, e)
    b.children = append(b.children, f)
    e.children = append(e.children, g)
    codec := &Codec{}
    content := codec.serialize(a)
    fmt.Println(content)
    head := codec.deserialize(content)
    fmt.Println(codec.serialize(head) == content)
}

//  Don't submit this class 
type Node struct {
    val      int
    children []*Node
}

func NewNode1() *Node {
    ret := &Node{}
    ret.children = make([]*Node, 0)
    return ret
}

func NewNode2(_val int) *Node {
    ret := &Node{}
    ret.val = _val
    ret.children = make([]*Node, 0)
    return ret
}

func NewNode3(_val int, _children []*Node) *Node {
    ret := &Node{}
    ret.val = _val
    ret.children = _children
    return ret
}

//  Submit the following class 
type Codec struct {
}

func (this *Codec) serialize(root *Node) string {
    if root == nil { //  Empty tree ！ Go straight back to #
        return "#"
    }
    builder := ""
    this.serial(&builder, root)
    return builder
}

//  Now comes head
func (this *Codec) serial(builder *string, head *Node) {
    *builder += fmt.Sprint(head.val) + ","
    if len(head.children) > 0 {
        *builder += "[,"
        for _, next := range head.children {
            this.serial(builder, next)
        }
        *builder += "],"
    }
}

func (this *Codec) deserialize(data string) *Node {
    if data == "#" {
        return nil
    }
    splits := strings.Split(data, ",")
    queue := make([]string, 0)
    for _, str := range splits {
        queue = append(queue, str)
    }
    return this.deserial(&queue)
}

func (this *Codec) deserial(queue *[]string) *Node {
    v, _ := strconv.Atoi((*queue)[0])
    cur := NewNode2(v)
    *queue = (*queue)[1:]
    cur.children = make([]*Node, 0)
    if len(*queue) > 0 && (*queue)[0] == "[" {
        *queue = (*queue)[1:]
        for (*queue)[0] != "]" {
            child := this.deserial(queue)
            cur.children = append(cur.children, child)
        }
        *queue = (*queue)[1:]
    }
    return cur
}

The results are as follows ：

picture

---

Zuo Shen java Code