# LeetCode: 428. 序列化和反序列化 N 叉树¶

## 1、题目描述¶

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

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

## 2、解题思路¶

• 递归
• 使用左右括号作为分界点
(1((3((5)(6)))(2)(4)))
(3((5)(6)))
(5)
(6)
(2)
(4)


"""
# Definition for a Node.
class Node(object):
def __init__(self, val=None, children=None):
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
"""
if not root:
return ""
current = "(" + str(root.val)
if root.children:
current += "("
for node in root.children:
current += self.serialize(node)
current += ")"

current += ")"
return current

def deserialize(self, data: str) -> 'Node':
"""Decodes your encoded data to tree.

:type data: str
:rtype: Node
"""
if not data:
return None

left_index = data[1:].index("(") if "(" in data[1:] else -1
if left_index == -1:
node = Node(data[1:-1])
node.children = []
return node
else:
left_index += 2
length = len(data) - 2
current = Node(data[1:left_index - 1])
current.children = []
while left_index < length:
pre = left_index
left_count = 1
while left_count > 0:
left_index += 1
if data[left_index] == "(":
left_count += 1
if data[left_index] == ")":
left_count -= 1
left_index += 1
current.children.append(self.deserialize(data[pre:left_index]))

return current

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