297. Serialize and Deserialize Binary Tree

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.

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.

 

# 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:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        data=[]
        if root:
            queue=deque()
            queue.append(root)
            
            while queue:
                cur=queue.popleft()
                
                if cur:
                    data.append(cur.val)
                    queue.append(cur.left)
                    queue.append(cur.right)
                else:
                    data.append('#')
        return ' '.join(map(str,data))
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        # exception
        if len(data)==0:
            return None
        
        data_list=data.split(' ')
        reader=0
        root=TreeNode(int(data_list[reader]))
        reader+=1
        
        queue=deque()
        queue.append(root)
        
        while queue:
            cur=queue.popleft()
            
            # set left
            val=''
            if reader >= len(data_list):
                val='@'
            else:
                val=data_list[reader]
                reader+=1
            
            if val!='#' and val!='@':
                cur.left=TreeNode(int(val))
                queue.append(cur.left)
            
            # set right
            val=''
            if reader >= len(data_list):
                val='@'
            else:
                val=data_list[reader]
                reader+=1
            
            if val!='#' and val!='@':
                cur.right=TreeNode(int(val))
                queue.append(cur.right)
            
        return root
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))