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 a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure
Test Cases
Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Explanation:
1
/ \
2 3
/ \
4 5
Example 2:
Input: root = []
Output: []
Solution
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
StringBuilder sb=new StringBuilder();
dfs(root,sb);
return sb.toString();
}
private void dfs(TreeNode x, StringBuilder sb) {
if (x==null) {
sb.append("null ");
return;
}
sb.append(String.valueOf(x.val));
sb.append(' ');
dfs(x.left,sb);
dfs(x.right,sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
String[] node=data.split(" ");
int[] d=new int[1];
return dfs(node,d);
}
private TreeNode dfs(String[] node, int[] d) {
if (node[d[0]].equals("null")) {
d[0]++;
return null;
}
TreeNode x=new TreeNode(Integer.valueOf(node[d[0]]));
d[0]++;
x.left=dfs(node,d);
x.right=dfs(node,d);
return x;
}
}
// 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));# Definition for a binary tree node.
class TreeNode(object):
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
s = []
self._serial(root, s)
return ' '.join(s)
def _serial(self, root, s):
if not root:
s.append("null")
return
s.append(str(root.val))
self._serial(root.left, s)
self._serial(root.right, s)
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
pos = [0]
arr = data.split(' ')
return self._deserial(arr, pos)
def _deserial(self, arr, pos):
if arr[pos[0]] == "null":
pos[0] += 1
return None
node = TreeNode(arr[pos[0]])
pos[0] += 1
node.left = self._deserial(arr, pos)
node.right = self._deserial(arr, pos)
return node
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))