Serialize and deserialize a binary tree#

Levels: level-5

Data structures: tree

Practice Link#

LeetCode

Description#

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.

Note:

Do not use class member/global/static variables to store states.
Your serialize and deserialize algorithms should be stateless.

Clarification:

The below 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.

Example#

text

1You may serialize the following tree:
2    1
3   / \
4  2   3
5     / \
6    4   5
7
8as "[1,2,3,null,null,4,5]"

Python Solution#

 1# Definition for a binary tree node.
 2class TreeNode(object):
 3    def __init__(self, x):
 4        self.val = x
 5        self.left = None
 6        self.right = None
 7
 8
 9class Codec:
10    def serialize(self, root):
11        """Encodes a tree to a single string.
12        
13        :type root: TreeNode
14        :rtype: str
15        """
16        def doit(node):
17            if node:
18                vals.append(str(node.val))
19                doit(node.left)
20                doit(node.right)
21            else:
22                vals.append('#')
23
24        vals = []
25        doit(root)
26        return ' '.join(vals)
27
28    def deserialize(self, data):
29        """Decodes your encoded data to tree.
30        
31        :type data: str
32        :rtype: TreeNode
33        """
34        def doit():
35            val = next(vals)
36            if val == '#':
37                return None
38            node = TreeNode(int(val))
39            node.left = doit()
40            node.right = doit()
41            return node
42
43        vals = iter(data.split())
44        return doit()
45
46
47# codec = Codec()
48# codec.deserialize(codec.serialize(root))