Serialize and Deserialize N-ary Tree

Intuition

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.

Solution


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