Given the root node of a tree , serialize it into a string.
Given a serialized string , construct a tree and return the true node.
Try out the solution here:
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
Solution:
Serialization:
First do a preorder traversal of the tree and store the node values in a string.
If node is null store the string value “null”.
Separate each value using a delimiter like “,” (comma)
Deserialization:
Convert the comma separated string value representing preorder traversal of the string into a list of string values.
Remove one value by one .(Use LinkedList since removal is faster for linked lists than array lists.
This way you will be constructing a node using the topmost value.
If the value is null return a null tree node.
Else construct a tree node using the first value , remove it.
And then construct the left sub tree using the remaining value recursively.
Also construct the right sub tree using the remaining value recursively.
Here is the code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
StringBuilder sb = new StringBuilder();
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
return serializeNodes(root).toString();
}
public StringBuilder serializeNodes(TreeNode node){
if(node==null){
sb.append("null,");
}else{
sb.append(String.valueOf(node.val)+",");
serializeNodes(node.left);
serializeNodes(node.right);
}
return sb;
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] nodes = data.split(",");
List<String> nodeList = new LinkedList<String>(Arrays.asList(nodes));
return deserializeNodes(nodeList);
}
public TreeNode deserializeNodes(List<String> nodes){
if(nodes.get(0).equals("null")){
nodes.remove(0);
return null;
}
Integer value = Integer.parseInt(nodes.get(0));
nodes.remove(0);
TreeNode node = new TreeNode(value);
node.left = deserializeNodes(nodes);
node.right = deserializeNodes(nodes);
return node;
}
}
// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));
Time complexity:
We traverse through each node in both the cases so time complexity is O(n) where n is the number of nodes.
Space complexity:
Serialization:
For serialization we make n recursive calls so space complexity is O(n)
Deserialization:
Here again we make n recursive calls.
Also we create a new Tree of size n.
So total time complexity is O(2n), ignoring the constant it is O(n)
That’s it!
Leave a Reply