# 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
        """
        if not root:
            return []
        stack = list()
        res = list()
        stack.append(root)
        while stack:
            tmp = stack.pop(0)
            if not tmp:
                res.append(None)
            else:
                res.append(tmp.val)
                stack.append(tmp.left)
                stack.append(tmp.right)
        return res



        
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == []:
            return None
        root = TreeNode(data.pop(0))
        stack = [root,]
        while stack:
            # print(stack)
            tmp = stack.pop(0)
            left = data.pop(0)
            right = data.pop(0)
            

            if left != None:
                tmp.left = TreeNode(left)
                stack.append(tmp.left)
            else:
                tmp.left = None
            
            if right != None:
                tmp.right = TreeNode(right)
                stack.append(tmp.right)
            else:
                tmp.right = None
        return root


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