# 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 do_serialize(self, root):
        """Recursively traverse Tree and creates list with None for empty leafs
        :type root: TreeNode
        :rtype: str
        """
        if root is not None:
            return [root.val] + self.do_serialize(root.left) + self.do_serialize(root.right)
        else:
            return [None]

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        return self.do_serialize(root)

    def do_deserialize(self, data):
        """ Recursively re-create Tree
        :type data: Iterator object for list
        :rtype: TreeNode
        """
        val = next(data)
        if val is None:
            return None

        root = TreeNode(val)
        root.left = self.do_deserialize(data)
        root.right = self.do_deserialize(data)
        return root

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        :type data: str
        :rtype: TreeNode
        """
        return self.do_deserialize(iter(data))