297. Serialize and Deserialize Binary Tree

# 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
        """
        # time O(N) space O(N)
        res = []
        def pre(node):
            if not node:
                res.append('#')
            else:
                res.append(str(node.val))
                pre(node.left)
                pre(node.right)
        pre(root)
        return ','.join(res)

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        #time O(N) space O(N)
        def build():
            if q :
                val = q.popleft()
                if val =='#':
                    return None
                node = TreeNode(int(val))
                node.left = build()
                node.right = build()
                return node
        q = collections.deque(d for d in data.split(','))
        return build()

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