<aside> 👉🏿 문제 링크

</aside>

사전 개념

<aside> 👉🏿 이진 트리의 특징과 표현

이진 트리 데이터 구조는 논리적인 구조이다. 이를 파일이나 디스크에 저장하기 위해서는

물리적인 형태로 바꿔줘야 하는데, 이를 직렬화라고 한다. 반대는 역직렬화이다.

</aside>

문제 정리

<aside> 👉🏿 이진 탐색 트리인 root가 주어지면 이를 직렬화 했다가 역직렬화로 다시 되돌아오게끔 구현해라.

</aside>

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

접근방법

<aside> 👉🏿 직렬화

큐를 이용해서 bfs 방식으로 탐색하면 순서대로 직렬화가 가능하다.

None이란 값은 문자형으로 표시할 수 없기 때문에 ‘#’으로 표시한다.

역직렬화

직렬화한 리스트의 인덱스를 하나씩 돌면서 순서대로 트리를 구성한다.

</aside>

코드 진행

<aside> 👉🏿 직렬화 구현

</aside>

def serialize(self, root):
        if root is None:
            return '#'
        list = []
        queue = collections.deque([root])
        while queue:
            node = queue.pop()
            if node:
                queue.append(node.left)
                queue.append(node.right)
                list.append(node.val)
            else :
                list.append("#")
        return list

<aside> 👉🏿 역직렬화

</aside>

def deserialize(self, data):
        if data == "#":
            return None

        nodes = data

        root = TreeNode(int(nodes[0]))
        queue = collections.deque([root])
        index = 1
        while queue:
            node = queue.popleft()
            if nodes[index] != "#":
                node.left = TreeNode(int(nodes[index]))
                queue.append(node.left)
            index += 1

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