[LeetCode/Python] 297.이진 트리 직렬화 & 역직렬화(Serialize and Deserialize Bonary Tree)

 

 

 

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

 

즉 다음과 같은 트리는 [1,2,3,null,,null,4,5] 형태로 직렬화할 수 있을 것이다.

 

 

 

1. 직렬화 & 역직렬화 구현

 

(1) 직렬화

 

def serialize(self, root):
        # BFS로 구현
        queue = collections.deque([root])
        output = ['#']
        while queue:
            node = queue.popleft()
            if node:
                queue.append(node.left)
                queue.append(node.right)
 
                output.append(str(node.val))
            else:
                output.append('#')
        return ' '.join(output)

 

해설

 

DFS로도 구현할 수 있지만

 

직관적으로 직렬화하기 위해 BFS로 구현하였다.

 

output에 index 1부터 채워 나가는데

 

node가 None일 경우 '#'을 넣어주었다.

 

최종적으로 str 값을 출력해야 하므로

 

리스트의 값들을 합쳐서 str로 리턴했다.

 

 

 

 

(2) 역직렬화

 

 

def deserialize(self, data):
        # 예외 처리
        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

 

해설

 

root가 None 값이 주어질 경우

 

data에는 '# #'이 들어가게 예외처리를 해주었다.

 

(한번 해봐라)

 

nodes를 통해 data를 다시 리스트화 해주었고

 

root가 우리가 최종적으로 리턴할 트리이다.

 

어차피 nodes에는 순서대로 값이 들어있으니까

 

index를 통해 root에 잎사귀들을 추가해준다.