This page explains Java solution to problem Serialize and Deserialize N-ary Tree
using Tree
data structure.
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 de-serialized to the original tree structure.
Example 1:Input:public String serialize(Node root)
package com.vc.hard;
import java.util.*;
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val, List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class SerializeAndDeserializeNAryTree {
// Encodes a tree to a single string.
public String serialize(Node root) {
StringBuilder sb = new StringBuilder();
serialize(root, sb);
return sb.toString();
}
private void serialize(Node root, StringBuilder sb) {
if(root == null) {
sb.append("NULL ");
}
else {
int size = root.children.size();
sb.append(root.val);
sb.append(",");
sb.append(size);
sb.append(" ");
for(Node child: root.children) {
serialize(child, sb);
}
}
}
// Decodes your encoded data to tree.
public Node deserialize(String data) {
String[] arr = data.split(" ");
Queue<String> q = new LinkedList<>();
for(String d: arr) q.offer(d);
return deserialize(q);
}
private Node deserialize(Queue<String> q) {
String e = q.poll();
if(e.equals("NULL")) return null;
else {
String[] qArr = e.split(",");
int val = Integer.parseInt(qArr[0]);
int size = Integer.parseInt(qArr[1]);
List<Node> children = new ArrayList<>();
Node node = new Node(val, children);
for(int i = 0; i < size; i++) {
children.add(deserialize(q));
}
return node;
}
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
O(N) Where
N is total number of elements in an input n-ary tree.
O(N) Where
N is total number of elements in an input n-ary tree.