greentea31's Note

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

풀이 과정

이진 트리를 직렬화(일자로) 했다가 다시 역직렬화 하는 문제이다.

BFS로 트리를 순회하면서, 방문 순서대로 문자열에 넣었다. 방문한 노드가 실제 존재하지 않는 노드라면, 문자열에 #을 추가하게끔 하였다. 역직렬화 과정중 문자열에서 각 노드의 값을 다시 추출하기 편하도록 문자열에서의 노드들의 값은 공백으로 구분하게끔 했다.

예시와 같은 트리를 BFS로 방문하면서 앞서 언급한대로 직렬화 한다면 serial = "1 2 3 # # 4 5"가 직렬화된 문자열로 저장될 것이다.

역직렬화 과정때도 BFS 과정을 통해 다시 트리로 바뀌게끔 구현하였다. "1 2 3 # # 4 5" 라는 문자열이 다시 위의 그림과 같이 역직렬화 되도록 구현하였다. 말로 풀어 설명하는 것보다는 코드를 읽으면 이해가 갈 것이다.

소스 코드

class Codec:

    def serialize(self, root):
        serial = ""
        Q = deque([root])
        while Q:
            cur_node = Q.popleft()
            if not cur_node:
                continue
            serial += str(cur_node.val)
            serial += ' '
            if cur_node.val == '#':
                continue
            if cur_node.left:
                Q.append(cur_node.left)
            else:
                Q.append(TreeNode('#'))
            if cur_node.right:
                Q.append(cur_node.right)
            else:
                Q.append(TreeNode('#'))
        
        while serial and serial[-1] == '#':
            serial = serial[:-1]
        
        return serial
        

    def deserialize(self, data):
        index = 0
        data = data.split()
        length = len(data)
        if length == 0:
            return None
        if data[index] != '#':
            root = TreeNode(data[index])
            index += 1
        if index >= length:
            return root
        Q = collections.deque([root])
        
        while Q:
            cur_node = Q.popleft()
            if data[index] != '#':
                cur_node.left = TreeNode(data[index])
                Q.append(cur_node.left)
            index += 1
            if index >= length:
                return root
            if data[index] != '#':
                cur_node.right = TreeNode(data[index])
                Q.append(cur_node.right)
            index += 1
            if index >= length:
                return root
        
        return root