[파이썬 알고리즘 인터뷰][트리] 이진 트리 직렬화 & 역직렬화

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

직렬화 / 역직렬화 구현

 

책에서 구현된 코드

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)

    # 역직렬화
    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

 

기억해야할 기법

• 직렬화 기법
  
  • 어떤 구분자를 사용할지 고려할 것
• DFS / 재귀도 고려해볼 것
  • 공간복잡도를 줄일 수 있는 방법도 생각해볼 것

 

내가 구현한 코드

class Codec:
    def serialize(self, root):
        q = deque([root])
        s = []

        while q:
            node = q.popleft()
            if node:
                s.append(str(node.val))
                q.append(node.left)
                q.append(node.right)
            else:
                s.append(" ")

        return ",".join(s)


    def deserialize(self, data):
        if len(data) == 0 or data[0] == " ":
            return None

        data = data.split(",")
        root = TreeNode(int(data[0]))
        q = deque([root])
        for i in range(1, len(data), 2):
            node = q.popleft()
            if data[i] != " ":
                node.left = TreeNode(int(data[i]))
                q.append(node.left)
            if i+1 < len(data) and data[i+1] != " ":
                node.right = TreeNode(int(data[i+1]))
                q.append(node.right)

        return root

• 코드가 흡사하고 결과도 비슷함

퍼센테이지가 이뻐서 박제