[LeetCode] 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]]. Note that this is just an example, you do not necessarily need to follow this format.

Or you can follow LeetCode's level order traversal serialization format, where each group of children is separated by the null value.

For example, the above tree may be serialized as [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14].

You do not necessarily need to follow the above suggested formats, there are many more different formats that work so please be creative and come up with different approaches yourself.

Constraints:

The height of the n-ary tree is less than or equal to 1000
The total number of nodes is between [0, 10^4]
Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.

N叉树的序列化和反序列化。题意跟297题几乎一样，唯一的不同是从二叉树换成了N叉树。

思路跟297题很接近，也是BFS层序遍历。首先是序列化，我们依然需要一个queue，当遇到一个节点的时候，我们把它放入queue；放入queue的同时，我们在stringbuilder里面记录node.val + "," + node.children.size() + ","。也就是说我们需要记录当前节点的val + 当前节点的孩子节点的个数。这里我选择用逗号隔开。从queue中poll出一个当前节点的同时，我们需要把这个节点的val和其孩子节点个数也记入stringbuilder。

反序列化的时候，首先我们还是把input string根据逗号分割开来，变成一个string array strs。此时我们需要两个queue，一个Queue<Node> queue负责处理当前节点，另一个Queue<Integer> childQueue负责记录当前节点的孩子节点的个数。首先strs的第一个元素strs[0]一定是根节点val，我们把他变成一个node加入queue；接着第二个元素是根节点的孩子个数，我们把这个数字放入childQueue。此时开始从queue中弹出一个元素，这是根节点；再从childQueue弹出一个元素N，这个数字是根节点的孩子节点的个数。我们再从strs里面拿出N个元素，这些元素是当前节点的孩子节点，我们把他们一一做成node，再放入queue。如此循环直到遍历完strs。

时间O(n)

空间O(n)

 1 class Codec {
 2 
 3     // Encodes a tree to a single string.
 4     public String serialize(Node root) {
 5         // corner case
 6         if (root == null) {
 7             return "";
 8         }
 9 
10         // normal case
11         StringBuilder sb = new StringBuilder();
12         Queue<Node> queue = new LinkedList<>();
13         queue.offer(root);
14         // current node + , + children size + ,
15         sb.append(root.val).append(",").append(root.children.size()).append(",");
16         while (!queue.isEmpty()) {
17             Node cur = queue.poll();
18             for (Node node : cur.children) {
19                 queue.offer(node);
20                 // current node + , + children size + ,
21                 sb.append(node.val).append(",").append(node.children.size()).append(",");
22             }
23         }
24         return sb.toString();
25     }
26 
27     // Decodes your encoded data to tree.
28     public Node deserialize(String data) {
29         // corner case
30         if (data.length() == 0) {
31             return null;
32         }
33 
34         // normal case
35         // current node + , + children size + ,
36         String[] nodes = data.split(",");
37         Queue<Node> queue = new LinkedList<>();
38         // count how many children nodes for the current node
39         Queue<Integer> childQueue = new LinkedList<>();
40         Node root = new Node(Integer.valueOf(nodes[0]));
41         queue.offer(root);
42         childQueue.offer(Integer.valueOf(nodes[1]));
43         int i = 2;
44         while (!queue.isEmpty()) {
45             Node cur = queue.poll();
46             cur.children = new ArrayList<>();
47             int n = childQueue.poll();
48             for (int j = 0; j < n; j++) {
49                 Node child = new Node(Integer.valueOf(nodes[i++]));
50                 childQueue.offer(Integer.valueOf(nodes[i++]));
51                 queue.offer(child);
52                 cur.children.add(child);
53             }
54         }
55         return root;
56     }
57 }
58 
59 // Your Codec object will be instantiated and called as such:
60 // Codec codec = new Codec();
61 // codec.deserialize(codec.serialize(root));