[LEET CODE] 297. Serialize and Deserialize Binary Tree

# Problem

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.   Constraints: The number of nodes in the tree is in the range [0, 104]. -1000 <= Node.val <= 1000

 

# My Answer

class Codec:

    def serialize(self, root):
        if not root:
            return root
        result=[]
        def bfs(queue):
            while queue:
                if not queue:
                    return result
                node = queue.pop(0)
                if node is None:
                    result.append("#")
                else:
                    result.append(node.val)
                    queue.append(node.left)
                    queue.append(node.right)
            return result
        result = bfs([root])
        return result

    def deserialize(self, data):
        if not data:
            return data
        root = TreeNode(data.pop(0))
        def BFS(queue):
            if not queue:
                return 
            if not data:
                return
            while queue:
                node = queue.pop(0)
                n = data.pop(0)
                if n!="#":
                    node.left = TreeNode(n)
                    queue.append(node.left)
                else:
                    node.left = None
                n = data.pop(0)
                if n!="#":
                    node.right = TreeNode(n)
                    queue.append(node.right)
                else:
                    node.right = None 
    
            return root
        return BFS([root])
        

 

# Solution 1 - 직렬화 & 역직렬화 구현

import collections

class Codec:
    # 직렬화
    def serialize(self, root: TreeNode) -> str:
        queue = collections.deque([root])
        result = ['#']
        # 트리 BFS 직렬화
        while queue:
            node = queue.popleft()
            if node:
                queue.append(node.left)
                queue.append(node.right)

                result.append(str(node.val))
            else:
                result.append('#')
        return ' '.join(result) # 문자열 형태로 반환한다 -> deserialize에서 사용

    # 역직렬화
    def deserialize(self, data: str) -> TreeNode:
        # 예외 처리
        if data == '# #':
            return None

        nodes = data.split() # 리스트로

        root = TreeNode(int(nodes[1]))
        queue = collections.deque([root])
        index = 2
        # 빠른 런너처럼 자식 노드 결과 먼저 확인 후 큐 삽입
        while queue:
            node = queue.popleft()
            if nodes[index] is not '#':
                node.left = TreeNode(int(nodes[index]))
                queue.append(node.left)
            index += 1

            if nodes[index] is not '#':
                node.right = TreeNode(int(nodes[index]))
                queue.append(node.right)
            index += 1
        return root

예제 1번의 트리를 배열로 표시하면

0  1   2   3   4   5   6   7

#  A   B  C   #   #   D   E

 

null 을 '#' 으로 표현

 

deque 자료형으로 popleft() 사용

 

인덱스를 하나씩 더해가면서 null이 아닌 경우 현재 노드에 이어붙인다