428. Serialize and Deserialize N-ary 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 an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure.
For example, you may serialize the following 3-ary tree
as [1 [3[5 6] 2 4]]. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Note:
Nis in the range of[1, 1000]- Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.
| /** | |
| * Definition for a node. | |
| * public class Node { | |
| * int val; | |
| * List<Node> children; | |
| * Node(int x) { val = x;} | |
| * } | |
| */ | |
| class Codec { | |
| // Encodes N-ary tree to a single string. | |
| public String serialize(Node root) { | |
| if (root == null) { | |
| return ""; | |
| } | |
| List<String> ans = new ArrayList<String>(); | |
| serializeHelper(root, ans); | |
| return String.join(",", ans); | |
| } | |
| public void serializeHelper(Node node, List<String> ans) { | |
| if (node == null) { | |
| return; | |
| } | |
| ans.add(String.valueOf(node.val)); | |
| ans.add(String.valueOf(node.children.size())); | |
| for (Node child: node.children) { | |
| serializeHelper(child, ans); | |
| } | |
| } | |
| // Decodes your encoded data to tree. | |
| public Node deserialize(String data) { | |
| if (data == null || data.length() == 0) { | |
| return null; | |
| } | |
| String[] tokens = data.split(","); | |
| Queue<String> q = new LinkedList<String>(Arrays.asList(tokens)); | |
| return deserializeHelper(q); | |
| } | |
| private Node deserializeHelper(Queue<String> q) { | |
| Node node = new Node(Integer.parseInt(q.poll(), 10), new ArrayList<Node>()); | |
| int size = Integer.parseInt(q.poll(), 10); | |
| for (int i = 1; i <= size; i++) { | |
| node.children.add(deserializeHelper(q)); | |
| } | |
| return node; | |
| } | |
| } | |
| // Your Codec object will be instantiated and called as such: | |
| // Codec codec = new Codec(); | |
| // codec.deserialize(codec.serialize(root)); |
