题目

序列化是指将一个数据结构转化为位序列的过程，因此可以将其存储在文件中或内存缓冲区中，以便稍后在相同或不同的计算机环境中恢复结构。

设计一个序列化和反序列化 N 叉树的算法。

序列化/反序列化算法的算法实现没有限制。你只需要保证 N 叉树可以被序列化为一个字符串并且该字符串可以被反序列化成原树结构即可。

例如，你需要序列化下面的 3-叉 树。

image.png

为 [1 [3[5 6] 2 4]]。你不需要以这种形式完成，你可以自己创造和实现不同的方法。

注意：

  • N 的范围在 [1, 1000]
  • 不要使用类成员/全局变量/静态变量来存储状态。你的序列化和反序列化算法应是无状态的。

    方案一（python pickle）

  1. """
  2. # Definition for a Node.
  3. class Node(object):
  4.     def __init__(self, val=None, children=None):
  5.         self.val = val
  6.         self.children = children
  7. """
  8. import pickle
  9. class Codec:
  11.     def serialize(self, root: 'Node') -> str:
  12.         """Encodes a tree to a single string.
  14.         :type root: Node
  15.         :rtype: str
  16.         """
  17.         return pickle.dumps(root)
  19.     def deserialize(self, data: str) -> 'Node':
  20.         """Decodes your encoded data to tree.
  22.         :type data: str
  23.         :rtype: Node
  24.         """
  25.         return pickle.loads(data)
  28. # Your Codec object will be instantiated and called as such:
  29. # codec = Codec()
  30. # codec.deserialize(codec.serialize(root))
  • 性能有点差

方案二

  1. """
  2. # Definition for a Node.
  3. class Node(object):
  4.     def __init__(self, val=None, children=None):
  5.         self.val = val
  6.         self.children = children
  7. """
  8. class Codec:
  10.     def serialize(self, root: 'Node') -> str:
  11.         """Encodes a tree to a single string.
  13.         :type root: Node
  14.         :rtype: str
  15.         """
  16.         if not root:
  17.             return ""
  18.         if not root.children:
  19.             return str(root.val) + " "
  21.         ret = f"{str(root.val)} [ "
  22.         for child in root.children:
  23.             ret += self.serialize(child)
  24.         ret += " ] "
  25.         return ret
  28.     def deserialize(self, data: str) -> 'Node':
  29.         """Decodes your encoded data to tree.
  31.         :type data: str
  32.         :rtype: Node
  33.         """
  34.         if not data:
  35.             return None
  37.         data = data.split()
  38.         if len(data) == 1:
  39.             return Node(val=int(data[0]), children=[])
  41.         stack = [] # 保存未构建完成的 children
  42.         children = []
  43.         for token in data:
  44.             if token == "[":
  45.                 stack.append(children)
  46.                 children = []
  47.             elif token == "]":
  48.                 before_children = stack.pop()
  49.                 before_children[-1].children = children
  50.                 children = before_children
  51.             else:
  52.                 children.append(Node(val=int(token), children=[]))
  54.         return children[0]
  57. # Your Codec object will be instantiated and called as such:
  58. # codec = Codec()
  59. # codec.deserialize(codec.serialize(root))

原文

https://leetcode-cn.com/explore/learn/card/n-ary-tree/161/conclusion/627/