Leetcode 765 Solution

This article provides solution to leetcode question 765 (serialize-and-deserialize-n-ary-tree)

https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree

Solution

``````"""
# 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 ""

ans = []
def _serialize(node):
if not node:
return

ans.append(str(node.val))

if node.children:
ans.append('[')
for child in node.children:
_serialize(child)
ans.append(']')

_serialize(root)

return " ".join(ans)

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

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

tokens = data.split(' ')

if not tokens:
return None

i = 0
def _deserialize(layer = 0):
nonlocal i

v = int(tokens[i])
i += 1

node = Node()
node.val = v
node.children = []

if i == len(tokens) or tokens[i].isnumeric() or tokens[i] == ']':
return node

assert tokens[i] == '[', "Token is {}".format(tokens[i])

i += 1
while i < len(tokens) and tokens[i] != ']':
node.children.append(_deserialize(layer + 1))
i += 1

return node

return _deserialize()

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