[코테] 리트코드 트리 297. Serialize and Deserialize Binary Tree

297. Serialize and Deserialize Binary Tree

문제 링크

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

문제 설명

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.

제한 사항

• The number of nodes in the tree is in the range [0, 10^4].
• -1000 <= Node.val <= 1000

입출력 예 #1

1. Input : root = [1,2,3,null,null,4,5]
2. Output : [1,2,3,null,null,4,5]

입출력 예 #2

1. Input : root = []
2. Output : []

문제 풀이

재귀 탐색을 통해 두 개의 트리에서 동일 위치에 노드가 있을 경우네는 두 노드의 값을 합한다.

재귀 탐색을 통해서 진행하기에 마지막 순회한 노드인 루트 노드가 리턴된다.

class Codec:
    def serialize(self, root) -> 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)        

    def deserialize(self, data) -> 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