In this solution, I use the level order which is the same as the leetcode input data for N-ary tree.
To serialize the N-ary tree, we could simply do a level order traversal, add a null after visiting each node.
"""
# Definition for a Node.
class Node(object):
def __init__(self, val=None, children=None):
self.val = val
self.children = children
"""
from collections import deque
class Codec:
def serialize(self, root: 'Node') -> str:
"""Encodes a tree to a single string.
:type root: Node
:rtype: str
"""
if root is None:
return ""
level_order = [root.val, None]
queue = deque([root])
while queue:
current = queue.popleft()
for child in current.children:
level_order.append(child.val)
queue.append(child)
level_order.append(None)
while level_order and level_order[-1] is None:
level_order.pop()
return ','.join(map(str, level_order))
def deserialize(self, data: str) -> 'Node':
"""Decodes your encoded data to tree.
:type data: str
:rtype: Node
"""
if not data:
return None
level_order = data.split(',')
for i in range(len(level_order)):
level_order[i] = None if level_order[i] == 'None' else \
int(level_order[i])
level_order = deque(level_order)
root = Node(level_order.popleft(), [])
if not level_order:
return root
level_order.popleft()
queue = deque([root])
while queue:
parent = queue.popleft()
while True:
child = None
if level_order:
child = level_order.popleft()
if child is None:
break
child_node = Node(child, [])
parent.children.append(child_node)
queue.append(child_node)
return root
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))