Python 알고리즘 인터뷰 - 문제 47. 이진 트리의 직렬화 & 역직렬화

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

 

문제

이진 트리를 배열로 직렬화하고, 반대로 역직렬화하는 기능을 구현하라.

예제1

 

input :  root [1,2,3,null, null, 3, 4] -> TreeNode

output : [1,2,3, null, null, 4, 5] -> TreeNode

 

예제 2

input : root [] -> TreeNode

output : [] -> TreeNode

 

디폴트 코드 정의

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """

 

함수 하나가 실행되는 것이 아닌 다음과 같은 방식으로 실행된다.

ser = Codec()
deser = Codec()
ans = deser.deserialize(ser.serialize(root))

serialize 입력값은 tree node이고 반환값은 serialize된 "문자열"이다. 따라서 "1,2,3,None,5" 형식으로 반환해야 한다.

deserialize 입력값은 문자열이다. "1,2,3,None,5" 형태의 문자열을 split하여 TreeNode를 만든 후 반환해야한다.

 

풀이

개인 풀이

class Codec:
    def serialize(self, root):
        if not root:
            return ''

        node = root
        result = [node.val]
        queue = deque([node])
        while queue:
            node = queue.popleft()

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

            if len(queue) > 0:
                result.append(None if node.left is None else node.left.val)
                result.append(None if node.right is None else node.right.val)

        while result and result[-1] is None:
            result.pop()

        result_str = ','.join(map(str, result))
        return result_str

    def deserialize(self, data):
        if len(data) == 0:
            return None

        str_data_list = data.split(',')
        int_data_list = [int(item) if item != 'None' else None for item in str_data_list]

        root = node = TreeNode(int_data_list[0])
        queue = deque([node])

        i = 1
        while i < len(int_data_list):
            current = queue.popleft()
            if int_data_list[i] is not None:
                current.left = TreeNode(int_data_list[i])
                queue.append(current.left)
            i += 1
            if i < len(int_data_list) and int_data_list[i] is not None:
                current.right = TreeNode(int_data_list[i])
                queue.append(current.right)
            i += 1

        return root

serialize 함수의 경우 BFS 방식으로 탐색하면서 queue에 데이터가 있을 경우 리스트에 자식 노드 값을 추가하는 방식으로 구현하였다. 이를 통해 각 Node에 해당하는 값을 리스트에 저장할 수 있다. 

마지막 저장되는 None 데이터는 모두 pop하여 처리한다.

 

deserialize 함수는 리스트의 인덱스를 전진하면서 None이 아닌 경우 좌, 우 자식노드에 TreeNode를 생성 및 연결하고 생성된 노드를 queue에 push한다. 리스트의 인덱스가 끝날 때까지 해당 로직을 반복하면 트리가 생성이 완료된다.

책 풀이

class Codec:

    def serialize(self, root):
        result = ['#']
        queue = collections.deque([root])
        while queue:
            node = queue.popleft()

            if node:
                queue.append(node.left)
                queue.append(node.right)

                result.append(str(node.val))
            else:
                result.append('#')

        while result and result[-1] == '#':
            result.pop()

        return ' '.join(result)

    def deserialize(self, data):
        if len(data) == 0:
            return None

        data = data.split(' ')

        root = TreeNode(int(data[1]))
        queue = collections.deque([root])
        idx = 2

        while idx < len(data):
            node = queue.popleft()
            if data[idx] is not '#':
                node.left = TreeNode(int(data[idx]))
                queue.append(node.left)
            idx += 1

            if idx < len(data) and data[idx] is not '#':
                node.right = TreeNode(int(data[idx]))
                queue.append(node.right)
            idx += 1

        return root

크게 2가지 부분이 다르다. 먼저 serialize에서 다음 구문이 서로 다르다.

[기존]

while queue:
    node = queue.popleft()

    if node.left:
        queue.append(node.left)
    if node.right:
        queue.append(node.right)

    if len(queue) > 0:
        result.append(None if node.left is None else node.left.val)
        result.append(None if node.right is None else node.right.val)

 

[신규]

while queue:
    node = queue.popleft()

    if node:
        queue.append(node.left)
        queue.append(node.right)

        result.append(str(node.val))
    else:
        result.append('#')

 

트리의 직경에서 BFS로 node의 left, right가 존재했을 때 queue에 push했는데 이 경우는 None을 queue에 넣지 않게 하기 위해 그렇다. 해당 문제는 None을 리스트에 넣어야하는 문제이기 때문에 node가 None이 아닐 경우 진행하고, not None일 경우 '#'을 추가한다. 보다 일반화된 BFS는 아랫쪽 코드임을 기억한다.

 

두번째는 None을 '#' 문자로 치환하는 것이다. 기존 코드는 None을 넣었기 때문에 deserialize에서 다음과 같이 int 리스트로 변환하였다.

str_data_list = data.split(',')
int_data_list = [int(item) if item != 'None' else None for item in str_data_list]

 

이 후 int 배열에서 None 문자를 체크하여 TreeNode를 연결한다.

while i < len(int_data_list):
    current = queue.popleft()
    if int_data_list[i] is not None:
        current.left = TreeNode(int_data_list[i])
        queue.append(current.left)
    i += 1
    if i < len(int_data_list) and int_data_list[i] is not None:
        current.right = TreeNode(int_data_list[i])
        queue.append(current.right)
    i += 1

 

신규 코드는 None 문자를 '#'으로 바꿨으므로 다음과 같이 '#'이 아닌 경우에만 TreeNode를 연결한다.

while idx < len(data):
    node = queue.popleft()
    if data[idx] is not '#':
        node.left = TreeNode(int(data[idx]))
        queue.append(node.left)
    idx += 1

    if idx < len(data) and data[idx] is not '#':
        node.right = TreeNode(int(data[idx]))
        queue.append(node.right)
    idx += 1