Description serialization is the process of converting a data structure or object into a bitstream so that it can be stored in a file or memory buffer or transmitted over a network connection link for later reconstruction in the same or another computer environment.

Design an algorithm to serialize and deserialize an n-fork tree. An n-fork tree is a rooted tree in which each node has no more than N children. There is no limit to how serialization/deserialization algorithms can be implemented. You just need to make sure that the n-tree can be serialized into a string, and that the string can be deserialized into the original tree structure.

For example, you could serialize the following 3-fork tree

Is [1 [3[5 6] 2 4]]. You don’t have to follow the format, be creative and come up with different approaches yourself.

Diagram model description

Online evaluation address

Sample 1

Input: {1,3,2,4 # 2, # 3 and 6 # 4 # 5 # 6} output: {1,3,2,4 # 2, # 3 and 6 # 4 # 5 # 6} : as shown aboveCopy the code

The sample 2

Input: {1,3,2#2#3} Output: {1,3,2#2#3} Interpretation: 1 / \ 32Copy the code

For the input directed graph, start from node 1 to traverse the construction string, and add the left parenthesis before traversing the son node, and add the right parenthesis after completion. Restore the n-fork tree again, the search starts on an open parenthesis, the number is saved, and exits on a close parenthesis.

The source code

/** * Definition for Directed graph. * class DirectedGraphNode { * int label; * ArrayList<DirectedGraphNode> neighbors; * DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); *}}; */ public class Solution { public int pos = 1; public String dfs(DirectedGraphNode root) { String ans=""; if(root == null) return ans; ans += "["; ans += String.valueOf(root.label); for(int i = 0; i < root.neighbors.size() ; i++) { ans += dfs(root.neighbors.get(i)); } ans += "]"; return ans; } public UndirectedGraphNode solve(String data) { int num = 0; while(data.charAt(pos) >= '0' && data.charAt(pos) <= '9') { num *= 10; num += data.charAt(pos) - '0'; pos++; } UndirectedGraphNode node = new UndirectedGraphNode(num); while(pos < data.length()) { if(data.charAt(pos) == '[' ) { ++pos; node.neighbors.add(solve(data)); } else if(data.charAt(pos) == ']') { pos++; return node; } } return null; } public String serialize(ArrayList<DirectedGraphNode> nodes) { String ans=""; if(nodes.size() == 0) return ans; return dfs(nodes.get(0)); } public UndirectedGraphNode deserialize(String data) { if(data.length() == 0) return null; return solve(data); }}Copy the code

For more information