[leetcode297]Serialize and Deserialize Binary Tree

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.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

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

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
from collections import deque
class Codec(object):

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        container = []
        que = deque([root])
        while que:
            cur = que.popleft()
            if cur is None:
                container.append('null')
                continue
            else:
                container.append(str(cur.val))
                que.append(cur.left)
                que.append(cur.right)

        return ",".join(container)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data:
            return None
        container = [TreeNode(int(ele)) if ele != 'null' else None for ele in data.split(',')]
        parent_idx = 0
        sub_idx = 1
        # root = None
        while sub_idx+1 < len(container) and parent_idx < len(container):
            parent = container[parent_idx]
            if parent is None:
                parent_idx += 1
                continue
            else:
                parent.left = container[sub_idx]
                parent.right = container[sub_idx+1]
                parent_idx += 1
                sub_idx += 2
        return container[0]


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))