The introduction

First of all, this is an algorithm question to go to Keep interview, search LeetCode also has… But Keep has changed it a bit

/** * Design a multi-fork tree serialization and deserialization algorithm. * * <p> * Each node of a multi-fork tree has a maximum of 100 child nodes, and each node has a field value of type Int. For example: * * * * / \ [1] * [2] [4] * / | \ \ * [1] [9] [8] [3] < / p > * * * * please use MyTree structure as much fork tree are defined. * /Copy the code

N fork tree

Let’s just say n-fork trees, where each node has at most N children. There is no limit to how the serialization/deserialization algorithm can work. We just need to make sure that the n-meta-tree can be serialized into a string and that the string can be deserialized into the original tree structure.

The idea was to do the same thing with binary tree serialization, which is to do it recursively, and to do it in a queue.

The code:

fun main(args: Array<String>) {
    //
    val mList = mutableListOf(TreeNode(2), TreeNode(4))
    mList[0].nodes.addAll(0, mutableListOf(TreeNode(1), TreeNode(9), TreeNode(8)))
    mList[1].nodes.addAll(0, mutableListOf(TreeNode(3)))
    val root = TreeNode(1, mList)

    //
    val serializeMyTreeString = serializeMyTree(root)
    println(serializeMyTreeString)
    println(deserializeMyTree(serializeMyTreeString))
}

data class TreeNode(
        val value: Int,
        val nodes: MutableList<TreeNode> = mutableListOf()
)

fun serializeMyTree(root: TreeNode): String {
    if (null == root) return "#"
    val sb = StringBuilder()
    order(root, sb)
    return sb.toString()
}

fun order(root: TreeNode, sb: StringBuilder) {
    if (root == null) {
        sb.append("#")
        return} // Add the length of each child node after it to terminate traversal. Use string.join () or sb.append(root.value).append().",").append(root.nodes.size)
    for (node in root.nodes) {
        sb.append(",") // Recursive order(node, sb)}} fun deserializeMyTree(s: String): TreeNode? {// The length of s is 0# character// remove the delimiter val arr = s.split(",".toRegex()).toTypedArray()
    if (arr.isEmpty()) returnVal queue: queue <String> = LinkedList() // Add datafor (item in arr) {
        queue.add(item)
    }
    returnorder(queue)!! } /** */ fun order(queue: queue <String>): TreeNode? Poll () println(val cur = queue.poll() println(val cur = queue.poll() println()"cur=$cur")
    if ("#" == cur) returnnull val nodes: MutableList<TreeNode> = mutableListOf() // Obtain the number of children of the head node val nodesSize = integer.valueof (queue.poll()) // Go through the queue notice no such list is includedfor (i in0 until nodesSize) {// Order (queue)? .let { nodes.add(it) } }return TreeNode(Integer.valueOf(cur), nodes)
}
Copy the code

After serialization:

1,2,2,3,1,0,9,0,8,0,4,1,3,0
Copy the code

Deserialization:

TreeNode(value=1, nodes=[TreeNode(value=2, nodes=[TreeNode(value=1, nodes=[]), TreeNode(value=9, nodes=[]), TreeNode(value=8, nodes=[])]), TreeNode(value=4, nodes=[TreeNode(value=3, nodes=[])])])

Copy the code