[알고리즘] 이진 트리 직렬화 & 역직렬화

이진 트리 직렬화 & 역직렬화

'이진 트리' 데이터 구조는 논리적인 구조다. 이를 파일이나 디스크에 저장하기 위해서는 물리적인 형태로 바꿔줘야 하는데, 이를 직렬화(Serialize)라고 한다. 반대는 역직렬화(Deserialize)다. 파이썬에서는 pickle이라는 직렬화 모듈을 기본으로 제공한다. 이 모듈의 이름으로 인해 파이썬 객체의 계층 구조를 바이트 스트림으로 변경하는 작업은 피클링이라고도 한다.

책 풀이

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Codec:
    # 직렬화
    def serialize(self, root: TreeNode) -> str:
        queue = collections.deque([root])
        result = ['#']
        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: str) -> TreeNode:
        # 예외 처리
        if data == '# #':
            return None
        
        nodes = data.split()
        
        root = TreeNode(int(nodes[1]))
        queue = collections.deque([root])
        index = 2
        while queue:
            node = queue.popeleft()
            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

BFS를 함께 돌리면서 문제를 푼다. None의 경우 문자열로 표현해야하니 #로 표현했다.