题目

序列化是将数据结构或者对象转换为连续的比特位的操作，进而可以将数据后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列/反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且这个字符串反序列化为原始的树结构。
image.png

思路

  1. # Definition for a binary tree node.
  2. # class TreeNode(object):
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.left = None
  6. #         self.right = None
  8. class Codec:
  10.     def serialize(self, root):
  11.         """Encodes a tree to a single string.        
  12.         :type root: TreeNode
  13.         :rtype: str
  14.         """
  15.         data = ''
  16.         def serialize_helper(root):
  17.             nonlocal data
  18.             if root is None:
  19.                 data += 'null '
  20.             else:
  21.                 data += str(root.val)
  22.                 data += ' '
  23.                 serialize_helper(root.left)
  24.                 serialize_helper(root.right)
  25.         serialize_helper(root)
  26.         print(data)
  27.         return data
  30.     def deserialize(self, data):
  31.         """Decodes your encoded data to tree.      
  32.         :type data: str
  33.         :rtype: TreeNode
  34.         """
  35.         if not data: return []
  36.         data = data.split()
  37.         print(data)
  38.         def deserialize(index):
  39.             if data[index] == 'null':
  40.                 return index, None
  41.             else:
  42.                 node = TreeNode(int(data[index]))
  43.                 l, left = deserialize(index+1)
  44.                 node.left = left
  45.                 r, right = deserialize(l+1)
  46.                 node.right = right
  47.                 return r, node
  48.         return deserialize(0)[1]
  52. # Your Codec object will be instantiated and called as such:
  53. # codec = Codec()
  54. # codec.deserialize(codec.serialize(root))