[리트코드] Serialize and Deserialize Binary Tree(python)

리트코드, Serialize and Deserialize Binary Tree(이진 트리 직렬화와 역직렬화)

TL;DR

• 트리(Tree)

문제 요약

1. 주어진 트리를 컴퓨터에서 다루기 쉬운 형태로 변형하는 직렬화(Serialize)하는 코드를 작성하라.
2. 직렬화된 트리를 다시 원래의 형태로 되돌리는 역직렬화(Deserialize)하는 코드를 작성하라.
3. 이진 트리를 입력받아 문자열 형태로 직렬화 해야 하고, 직렬화된 문자열을 다시 이진 트리로 역직렬화할 수 있어야 한다.

 

- 트리와 같이 논리적인 데이터 구조를 갖고 있는 자료 구조를 컴퓨터 내부에 저장하기 위해서는 물리적인 구조로 바꾸어주어야 할 필요가 있다. 이 때, 논리적인 데이터 구조에서 물리적인 데이터 구조로 변경하는 작업을 직렬화(Serialize)라고 부르고 그 반대의 경우를 역직렬화(Deserialize)라고 부른다.

- 문제에서는 트리를 직렬화하고 역직렬화하는 함수를 각각 구현할 것을 요구하고 있다.

- 직렬화 함수에서는 이진 트리를 입력받아 문자열을 반환하고, 역직렬화 함수에서는 직렬화된 문자열을 입력받아 다시 이진 트리로 역직렬화해야 한다.

입출력 형태

입출력 예시

 

- 입출력 예시에는 리스트의 형태로 나와있지만 각각은 리트코드에서 작성한 `TreeNode`의 형태로 되어 있다.

- 테스트 코드가 실행될 때, 주어진 입력을 직렬화하고 직렬화의 결과를 다시 역직렬화하여 입력과 같은 형태를 반환하도록 함수를 작성해야 한다.

풀이

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root: Optional[TreeNode]) -> str:
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root:
            return '1001'
        
        queue = collections.deque([root])
        Q = [(0, root.val)]
        level = 0
        
        def get_max_level(root: Optional[TreeNode]) -> int:
            queue = collections.deque([root])
            level = -1
            
            while queue:
                level += 1
                
                for i in range(len(queue)):
                    node = queue.popleft()
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                    
            return level
        
        MAX_LEVEL = get_max_level(root)
        
        while queue:
            level += 1
            if level > MAX_LEVEL:
                break
                
            for i in range(len(queue)):
                node = queue.popleft()

                if node.left:
                    queue.append(node.left)
                    heapq.heappush(Q, (level, node.left.val))
                else:
                    heapq.heappush(Q, (level, 1001))
                if node.right:
                    queue.append(node.right)
                    heapq.heappush(Q, (level, node.right.val))
                else:
                    heapq.heappush(Q, (level, 1001))
        
        return ' '.join([str(val) for _, val in Q])
        

    def deserialize(self, data: str) -> Optional[TreeNode]:
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if data == '1001':
            return None
        
        parsed_data = list(map(int, data.split(' ')))
        index = 0
        root = TreeNode(parsed_data[index])
        queue = collections.deque([root])
        index += 1
        
        while index < len(parsed_data) and queue:
            node = queue.popleft()

            if parsed_data[index] != 1001:
                node.left = TreeNode(parsed_data[index])
                queue.append(node.left)
            index += 1
            
            if parsed_data[index] != 1001:
                node.right = TreeNode(parsed_data[index])
                queue.append(node.right)
            index += 1
            
        return root
        
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))

- 직렬화 함수

이 함수는 이진 트리를 입력받아 직렬화한 문자열을 돌려주는 기능을 수행한다.

- 우선 이진 트리를 BFS로 순회하기 위한 queue를 선언하고 root를 넣어 초기화해둔다.

- 직렬화를 위해 트리 기반의 자료 구조인 힙`heapq`를 사용하여 문제를 해결하였다. 주어진 이진 트리를 순회하며 자식 노드들에 대한 정보를 저장할 Q를 선언하였다. 이 Q는 루트 노드에서부터 자식 노드들을 조회하며 (레벨 정보, 노드의 값)을 저장하게 된다. 파이썬에서 heapq는 최소 힙으로 구현되었기 때문에 Q는 입력받은 트리와 같은 형태의 트리라고 할 수 있다.

 

- 만약 자식 노드가 없는 형태라면 해당 노드에는 문제의 제약 조건에 따라 트리의 노드가 갖을 수 없는 값인 1001을 담도록 하였다. 비어 있는 노드임을 직렬화된 문자열에서는 1001이 있는지 없는지 확인을 통해 알 수 있다.

 

- `get_max_level`은 트리의 높이에 있는 모든 노드를 조회하였을 때 직렬화를 진행하지 않기 위해서 작성한 함수이다. 이 함수를 사용하지 않는다면 리프 노드의 자식 노드들까지 BFS로 탐색하게 되어 불필요한 노드 정보까지 Q에 저장되게 된다.

 

코드가 실행되고 나면 Q는 입력된 이진 트리와 같은 형태이면서 리스트의 형태로 접근할 수 있게 된다. Q의 튜플의 첫 번째 원소를 레벨 정보 이므로 이를 제외한 노드의 값 정보만 활용하여 문자열로 직렬화해준다.

예시 1의 입력이 주어졌을 때 직렬화과 완료된 결과는 "1 2 3 1001 1001 4 5"로 표현된다. 1001은 비어 있음을 의미한다.

 

- 역직렬화 함수

역직렬화 함수에서는 직렬화한 문자열을 바탕으로 다시 이진 트리의 형태로 반환하는 기능을 수행한다.

- 역직렬화 함수에서는 입력받은 직렬화한 결과가 1001이라면 비어 있는 이진 트리이므로 None을 반환한다.

- 그렇지 않은 경우에는 직렬화된 값을 이진 트리 노드 값에 할당하기 위해 리스트의 형태로 반환한다.

- 역직렬화할 이진 트리의 root를 반환한 직렬화 코드의 첫 번째 값으로 초기화하고 queue에 넣는다. BFS를 사용하여 queue를 순회하며 이진 트리를 만들어나간다.

- index는 왼쪽 자식 노드와 오른쪽 자식 노드를 구분하기 위해 사용한다. 직렬화된 트리는 왼쪽 자식 노드와 오른쪽 자식 노드 순서대로 저장이 되어 있다.

 

- BFS를 도는 동안 노드의 값이 1001이 아니라면, 즉 노드가 존재한다면 해당 노드를 만들고, 큐에 넣어 트리를 구성한다. 이를 통해 직렬화된 코드로부터 이진 트리를 만들 수 있다.

 

정리하자면,

1. 직렬화 함수 : 입력된 이진 트리를 heapq를 사용하여 이진 트리의 형태를 갖고 있는 리스트로 만들고 이를 문자열로 직렬화하여 반환한다.

2. 역직렬화 함수 : 직렬화된 문자열의 값을 사용하여 각 노드를 생성하고 BFS를 사용하여 이진 트리를 완성한다.