LeetCode 428: Serialize and Deserialize N-ary Tree Solution
Master LeetCode problem 428 (Serialize and Deserialize N-ary Tree), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
428. Serialize and Deserialize N-ary Tree
Problem Explanation
Explanation:
To serialize an N-ary tree means to convert it into a string representation that can be easily deserialized back into the original tree structure. The serialization and deserialization processes should be reversible.
For the serialization, we can perform a preorder traversal of the tree and append each node's value along with the number of its children. We can use a special character to indicate the end of children for each node. To deserialize, we read the serialized string and reconstruct the tree based on the preorder traversal.
Serialization Steps:
- Initialize an empty string to store the serialized form.
- Perform a recursive preorder traversal of the tree.
- Append the current node's value followed by the number of its children.
- Recursively serialize each child of the current node.
- Use a special character to indicate the end of children for each node.
Deserialization Steps:
- Initialize a pointer to keep track of the current position in the serialized string.
- Read the value and number of children for the current node.
- Create the current node with the value.
- Recursively deserialize each child by moving the pointer.
- Return the root node of the deserialized tree.
The time complexity for both serialization and deserialization is O(n), where n is the number of nodes in the N-ary tree. The space complexity for serialization is O(n) to store the serialized string, and for deserialization, it is also O(n) due to the call stack space used for recursion.
: :
Solution Code
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int val) {
this.val = val;
}
public Node(int val, List<Node> children) {
this.val = val;
this.children = children;
}
}
public class Codec {
// Encodes a tree to a single string.
public String serialize(Node root) {
if (root == null) return "";
StringBuilder sb = new StringBuilder();
serializeHelper(root, sb);
return sb.toString();
}
private void serializeHelper(Node node, StringBuilder sb) {
if (node == null) return;
sb.append(node.val).append(" ").append(node.children.size()).append(" ");
for (Node child : node.children) {
serializeHelper(child, sb);
}
sb.append("# ");
}
// Decodes your encoded data to tree.
public Node deserialize(String data) {
if (data.isEmpty()) return null;
String[] tokens = data.split(" ");
return deserializeHelper(tokens, new int[]{0});
}
private Node deserializeHelper(String[] tokens, int[] index) {
if (index[0] >= tokens.length || tokens[index[0]].equals("#")) {
index[0]++;
return null;
}
Node node = new Node(Integer.parseInt(tokens[index[0]++]));
int numChildren = Integer.parseInt(tokens[index[0]++]);
node.children = new ArrayList<>();
for (int i = 0; i < numChildren; i++) {
node.children.add(deserializeHelper(tokens, index));
}
return node;
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 428 (Serialize and Deserialize N-ary Tree)?
This page provides optimized solutions for LeetCode problem 428 (Serialize and Deserialize N-ary Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 428 (Serialize and Deserialize N-ary Tree)?
The time complexity for LeetCode 428 (Serialize and Deserialize N-ary Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 428 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 428 in Java, C++, or Python.