二叉树的序列化与反序列化-二叉树297-python

python

# 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
        """
        res = []
        def dfs(root):
            if not root:
                res.append(str(None))
                return
            
            res.append(str(root.val))
            dfs(root.left)
            dfs(root.right)
        dfs(root)
        
        return ','.join(res)
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        assert isinstance(data, str)
        ls = list(data.split(','))
        def reconstruction(ls):
            if ls[0] == 'None':
                ls.pop(0)
                root = None
                return root
            
            root = TreeNode(int(ls[0]))
            ls.pop(0)
            root.left = reconstruction(ls)
            root.right = reconstruction(ls)      

            return root
        
        return reconstruction(ls)
        

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