难度: Hard
Submission
运行时间: 44 ms
内存: 18.8 MB
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=None, children=[]):
self.val = val
self.children = children
"""
class Codec:
def serialize(self, root: 'Node') -> str:
"""Encodes a tree to a single string.
:type root: Node
:rtype: str
"""
def encode(node):
if not node:
return
res = str(node.val) + " "
hasChildren = len(node.children) > 0
if hasChildren:
res += "[ "
for i in range(len(node.children)):
res += encode(node.children[i])
if hasChildren:
res += " ] "
return res
if not root:
return ""
res = encode(root)
# print(res)
return res
def deserialize(self, data: str) -> 'Node':
"""Decodes your encoded data to tree.
:type data: str
:rtype: Node
"""
if not data:
return None
data = data.split(" ")
stack = []
curr = None
root = None
for s in data:
if s == '':
continue
if s == "[":
stack.append(curr)
elif s == "]":
stack.pop()
else:
node = Node(val=int(s))
if root == None:
root = node
else:
parent = stack[-1]
parent.children.append(node)
curr = node
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
Explain
这个题解使用递归的方式对 N 叉树进行前序遍历，将树的结构编码为字符串进行序列化。在反序列化时，通过维护一个栈来存储当前节点的父节点，以便正确地重建树的结构。序列化时，每个节点的格式为 "值 [子节点...] "，其中方括号内是该节点的子节点序列。反序列化时，遇到数字则创建节点，遇到 "[" 则将当前节点压栈，遇到 "]" 则弹出栈顶节点。通过这种方式，可以正确地还原 N 叉树。
时间复杂度: 序列化：O(n^2)，反序列化：O(n)
空间复杂度: 序列化：O(n+m)，反序列化：O(n+m)
```python
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=None, children=[]):
self.val = val
self.children = children
"""
class Codec:
def serialize(self, root: 'Node') -> str:
"""Encodes a tree to a single string.
:type root: Node
:rtype: str
"""
def encode(node):
if not node:
return
# 节点值加空格
res = str(node.val) + " "
hasChildren = len(node.children) > 0
if hasChildren:
# 如果有子节点，添加 "[ "
res += "[ "
# 递归处理子节点
for i in range(len(node.children)):
res += encode(node.children[i])
if hasChildren:
# 如果有子节点，添加 "] "
res += " ] "
return res
if not root:
return ""
res = encode(root)
# print(res)
return res
def deserialize(self, data: str) -> 'Node':
"""Decodes your encoded data to tree.
:type data: str
:rtype: Node
"""
if not data:
return None
data = data.split(" ")
stack = [] # 存储父节点的栈
curr = None # 当前节点
root = None # 根节点
for s in data:
if s == '':
continue
if s == "[":
# 遇到 "["，将当前节点压栈
stack.append(curr)
elif s == "]":
# 遇到 "]"，弹出栈顶节点
stack.pop()
else:
# 遇到数字，创建新节点
node = Node(val=int(s))
if root == None:
# 第一个节点作为根节点
root = node
else:
# 将新节点添加到父节点的子节点列表中
parent = stack[-1]
parent.children.append(node)
curr = node # 更新当前节点
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))
```
Explore
前序遍历首先访问根节点，然后递归地进行子节点的遍历。这种方式非常适合序列化和反序列化，因为它自然地保留了节点与其子树之间的层级关系，使得在反序列化时能够从树的根部开始逐步向下构建整个树结构。此外，前序遍历的序列化结果直观且易于实现，节点的父子关系清晰，处理起来更直接，无需额外记录节点间的关系，便于反序列化时树的重建。
使用空格和方括号区分节点和子节点的开始与结束在逻辑上是清晰的。然而，实际操作中如果树特别深或节点数特别多，确实可能导致解析上的复杂性增加，特别是对于深度递归的处理可能引起性能问题。此外，如果节点值中包含空格或特殊字符如方括号，会引入歧义或解析错误。通常需要对节点值进行适当的编码或转义处理，或者选择更安全的分隔符，以保证序列化和反序列化的过程中数据的完整性和准确性。
当前的序列化方法假设节点值为整型数。如果节点值为字符串或其他类型，该方法需要适当调整以支持这些类型。首先，需要确保节点值的字符串表示不含有用于分隔的特殊字符（如空格、方括号等）。如果存在这样的字符，需要引入转义机制或使用其他分隔字符。其次，反序列化时需要正确解析这些值并转换回原始类型。为了通用性，可以在序列化时明确标记数据类型，反序列化时据此恢复原始数据类型。
使用空字符串判断来跳过空格是一种简单的方法，但不是最优的。更高效的方式是在分割字符串时直接去除空条目。例如，可以使用 `data.strip().split()` 来确保首尾的空格被移除并正确分割字符串。此外，使用正则表达式或更加精确的字符串处理方法可以有效处理复杂或不规则的输入格式，避免错误解析。提前处理或清洗数据，去除不必要的空格或特殊字符，可以提高解析的效率和准确性。