leetcode-bt

297. Serialize and Deserialize Binary Tree.py

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

class Codec:
    """
    Thought Process:
        for 
    Note:
        Ref
    """
    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        self.data = []
        def write(n):
            if not n:
                # means null
                self.data.append("#") 
            else:
                self.data.append(str(n.val))
        def dfs(r):
            """pre-order"""
            write(r)
            if r:
                dfs(r.left)
                dfs(r.right)
        
        dfs(root)
        self.data = ",".join(self.data)
        return self.data
        
    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if len(data) == 0:
            return None
        data = data.split(",")
        print (data)
        q = collections.deque(data) # in order to alway get first element in O(1)
        def dfs(q):
            """pre-order"""
            if q[0] == "#":
                q.popleft()
                return None
            r = TreeNode(q[0])
            q.popleft()
            r.left = dfs(q)
            r.right = dfs(q)
            return r
    
        return dfs(q)

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