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

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

---

문제

• 트리 형태로 주어진 데이터를 문자열로 반환하고, 역으로 문자열로 주어진 데이터를 트리 형태로 반환하는 문제

---

직렬화

접근 방법: BFS

• BFS방식으로 한 층씩 순회하며 값을 리스트에 옮긴다. 존재하지 않는 노드의 경우 None을 넣으려 하였으나, 리스트를 하나의 문자열로 join하는 과정에서 None을 처리하지 못하는 에러가 발생해 그냥 아무것도 없는 문자열을 넣어주었다('').

• 리스트를 문자열로 바꾸는 과정에서 값을 구별하기 위해 csv파일처럼 구분자로 콤마(,)를 넣어주었다.
  

• 위와 같은 트리의 경우, 직렬화를 하면 '1,2,3,,,4,5'와 같은 형태로 반환된다.

코드

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """         
        q = collections.deque()
        q.append(root)
        values = []

        while q:
            node = q.popleft()
            if node:
                values.append(str(node.val))
                q.append(node.left)
                q.append(node.right)
            else:
                values.append('')
        return ','.join(values)

---

역직렬화

접근 방법

• 문자열을 받아오면 split()을 이용하여 콤마 단위로 분리해 다시 리스트 형태로 만들어주었다.

• 이 후, 완전 이진 트리 구조에서 자식 노드의 인덱스값이 부모노드의 두 배가 되는 것을 이용하여 트리를 만드려고 하였으나, 문제에서 주어진 트리는 완전 이진 트리가 아니므로 위에서 사용한 직렬화 방식으로는 인덱스의 값으로 노드의 위치를 특정할 수 없는 문제가 발생하였다.

• 따라서 데이터를 for문에 넣어 순회하며 직렬화를 했던 역순으로 트리구조를 채워나가는 방식을 사용하기로 했다. 코드는 리트코드의 코드를 참고하였다.

코드

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        if data == '':
            return None
        nodes = [None if val == '' else TreeNode(int(val)) for val in data.split(',')]
        kids = nodes[::-1]
        root = kids.pop()
        for node in nodes:
            if node:
                if kids:
                    node.left = kids.pop()
                if kids:
                    node.right = kids.pop()
        return root