Solution0 used post order traversal. Solution1 used pre order traversal and tricks to use python closure. Solution2 used bfs. Solution0 is recommended to use in on this problem.

tree_serialization.py

"""
Design an algorithm and write code to serialize and deserialize a binary tree.
Writing the tree to a file is called 'serialization'
and reading back from the file to reconstruct
the exact same binary tree is 'deserialization'.
There is no limit of how you deserialize or serialize a binary tree,
you only need to make sure you can serialize a binary tree to a string
and deserialize this string to the original structure.
Have you met this question in a real interview? Yes
Example
An example of testdata: Binary tree {3,9,20,#,#,15,7},
denote the following structure:
  3
 / \
9  20
  /  \
 15   7
Our data serialization use bfs traversal.
This is just for when you got wrong answer and want to debug the input.

You can use other method to do serializaiton and deserialization.
"""

### Python


"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""
class Solution0:
    '''
    @param root: An object of TreeNode, denote the root of the binary tree.
    This method will be invoked first, you should design your own algorithm
    to serialize a binary tree which denote by a root node to a string which
    can be easily deserialized by your own "deserialize" method later.
    '''
    def serialize(self, root):
        if not root:
            return ''

        def post_order(root):
            if root:
                post_order(root.left)
                post_order(root.right)
                ret[0] += str(root.val) + ','
            else:
                ret[0] += '#,'

        ret = ['']
        post_order(root)

        return ret[0][:-1]  # remove last ,

    '''
    @param data: A string serialized by your serialize method.
    This method will be invoked second, the argument data is what exactly
    you serialized at method "serialize", that means the data is not given by
    system, it's given by your own serialize method. So the format of data is
    designed by yourself, and deserialize it here as you serialize it in
    "serialize" method.
    '''
    def deserialize(self, data):
        if not data:
            return

        nodes = data.split(',')
        def post_order(nodes):
            if nodes[-1] == '#':
                nodes.pop()
                return None
            root = TreeNode(int(nodes.pop()))
            root.right = post_order(nodes)
            root.left = post_order(nodes)
            return root
        return post_order(nodes)

class Solution1:
    def serialize(self, root):
        if not root:
            return ''

        def pre_order(root):
            if root:
                ret[0] += str(root.val) + ','
                pre_order(root.left)
                pre_order(root.right)
            else:
                ret[0] += '#,'

        ret = ['']
        pre_order(root)

        return ret[0][:-1]  # remove last ,

    def deserialize(self, data):
        if not data:
            return

        nodes = data.split(',')
        self.i = 0
        def pre_order(nodes):
            if nodes[self.i] == '#':
                return None
            root = TreeNode(int(nodes[self.i]))
            self.i += 1
            root.left = pre_order(nodes)
            self.i += 1
            root.right = pre_order(nodes)
            return root
        return pre_order(nodes)


import collections
class Solution2:
    def serialize(self, root):
        if not root:
            return

        ret = []
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if node:
                queue.append(node.left)
                queue.append(node.right)
                ret.append(str(node.val))
            else:
                ret.append('#')
        return ','.join(ret)


    def deserialize(self, data):
        if not data:
            return
        nodes = data.split(',')
        root = TreeNode(int(nodes[0]))
        i = 1
        queue = collections.deque()
        queue.append(root)
        while queue:
            node = queue.popleft()
            if nodes[i] == '#':
                node.left = None
            else:
                t = TreeNode(int(nodes[i]))
                node.left = t
                queue.append(t)
            i += 1
            if nodes[i] == '#':
                node.right = None
            else:
                t = TreeNode(int(nodes[i]))
                node.right = t
                queue.append(t)
            i += 1
        return root


"""
第零种解法是后序遍历（推荐）， 在`serialize`的时候， 需要先左->右->中。 
  在`deserialize`的时候，因为是从最后一个值开始pop， 构成tree的时候， 就应该先中->右->左。
Solution0 used post order traversal. 

第一种解法是前序遍历， 其中巧妙的利用了python的closure， 在`serialize`中， 
  利用了list mutable 的特性， 修改了ret中的值。 `deserialize`中， 利用了`self.i`来储存`instance variable`。
Solution1 used pre order traversal and tricks to use python closure.

第二种解法是广度遍历。 在`deserialize`的时候， 保持一个`index i`，记录用过的node。
Solution2 used bfs. Solution0 is recommended to use in on this problem.
"""