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.
Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5]
Input: root =  Output: 
Input: root =  Output: 
Input: root = [1,2] Output: [1,2]
- The number of nodes in the tree is in the range
-1000 <= Node.val <= 1000
We can use breadth-first search in both serialize and deserialize. During serializing, we use breadth-first search to record all the node values into an array or a string in order. During deserializing, we follow a similar breadth-first search to creating the nodes and use an index pointer pointing to the next value in the array for creating a new node. In both serialize and deserialize processes, the queue would be only used to keep track of the nodes with values.
# 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 """ if not root: return  queue =  queue.append(root) results =  while queue: size = len(queue) for i in range(size): node = queue.pop(0) if node: results.append(node.val) queue.append(node.left) queue.append(node.right) else: results.append(None) return results def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if not data: return None index = 0 root = TreeNode(data[index]) queue =  queue.append(root) index += 1 while queue: size = len(queue) for i in range(size): node = queue.pop(0) if data[index] != None: node.left = TreeNode(data[index]) queue.append(node.left) index += 1 if data[index] != None: node.right = TreeNode(data[index]) queue.append(node.right) index += 1 return root # Your Codec object will be instantiated and called as such: # ser = Codec() # deser = Codec() # ans = deser.deserialize(ser.serialize(root))
- Time complexity: O(N)
- Space complexity: O(N)