[리트코드(LeetCode)] 297. Serialize and Deserialize Binary Tree - Python

Serialize and Deserialize Binary Tree - LeetCode

- <파이썬 알고리즘 인터뷰>를 학습하면서 수록된 코드를 참고하였습니다. - 

 

풀이

Tree 구조의 데이터를 직렬화 & 역직렬화 시키는 메소드를 구현하는 문제.

 

직렬화는 '이진 트리'와 같은 데이터 구조는 논리적 구조이기 때문에 이를 파일이나 디스크에 저장하기 위해서 물리적인 형태로 바꿔주는 것을 말한다. (역직렬화는 물리적인 형태를 논리적인 구조로 변경하는 것)

 

 

먼저 serialize() 메소드를 구현해보자.

이 문제에서는 TreeNode 구조를 직렬화 과정을 거쳐 str 타입으로 변환하고, str 타입 데이터를 TreeNode 구조로 역직렬화 시키는 메소드를 구현하는 것으로 이진 트리 형태의 데이터 구조를 배열 형태로 변환을 하고, 이 배열을 문자열로 변환시키는 방법으로 접근할 수 있다.

 

이진 트리를 root 노드부터 인덱스 값을 매겨가면서 왼쪽 -> 오른쪽 자식 노드 순서로 BFS 탐색을 하여 배열에 해당 인덱스에 노드 값을 저장한다. 노드가 있어야할 자리가 비어 있는 경우 'null' 처리를 한다.

queue = collections.deque([root])
result = []

while queue:
            node = queue.popleft()

            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append('null')

 

BFS 탐색이 끝나면 해당 배열을 공백을 기준으로 문자열로 변환하여 리턴한다.

return ' '.join(result)

 

deserialize() 메소드는 앞서 구현한 직렬화 메소드의 반대이다. 문자열 타입의 데이터를 입력 받아 이를 이진 트리 구조로 변환을 시킨다.

 

우선 문자열을 공백을 기준으로 분리한 배열로 변환을 한다. 이어서 배열의 원소들을 값으로 갖는 TreeNode 객체를 만들어 배열의 각 원소로 저장한다.

data = data.split()
for i, value in enumerate(data):
    data[i] = TreeNode(value)

 

이후 data 배열을 다시 한번 차례로 탐색하면서 해당 원소에 존재하는 TreeNode에게 자식 노드를 부여한다.

이진 트리 구조에서는 왼쪽 자식 노드의 인덱스 값은 현재 노드 인덱스에 *2를 한 값이고, 오른쪽 자식 노드의 인덱스 값은 현재 노드 인덱스에 *2 + 1 한 값을 갖는다는 규칙적인 패턴이 존재하기 때문에, 이를 이용하여 자식 노드가 되는 노드를 찾을 수 있다.

주의할 점은 배열은 0부터 시작하기 때문에 root 노드의 인덱스가 1부터 시작하는 것처럼 처리를 해줘야 원하는 답을 얻을 수 있다.

for i in range(1, len(data) + 1):
    # 왼쪽 자식 노드는 본인 인덱스 값 * 2
    if i * 2 <= len(data):
    data[i - 1].left = data[(i * 2) - 1]
    # 오른쪽 자식 노드는 본인 인덱스 값 * 2 + 1
    if i * 2 + 1 <= len(data):
        data[i - 1].right = data[(i * 2 + 1) - 1]

return data[0]

 

최종 코드는 다음과 같다.

class Codec:

	# 직렬화
    def serialize(self, root):
    	# 예외 처리
        if not root:
            return ''

        queue = collections.deque([root])
        result = []

        # bfs 방식으로 왼쪽 노드 -> 오른쪽 노드 순으로 순회
        while queue:
            node = queue.popleft()

            if node:
                result.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
            else:
                result.append('null')
        return ' '.join(result)

	# 역직렬화
    def deserialize(self, data):
    	# 예외 처리
        if len(data) == 0:
            return []

        data = data.split()
        for i, value in enumerate(data):
            data[i] = TreeNode(value)

        for i in range(1, len(data) + 1):
            # 왼쪽 자식 노드는 본인 인덱스 값 * 2
            if i * 2 <= len(data):
                data[i - 1].left = data[(i * 2) - 1]
            # 오른쪽 자식 노드는 본인 인덱스 값 * 2 + 1
            if i * 2 + 1 <= len(data):
                data[i - 1].right = data[(i * 2 + 1) - 1]

        return data[0]

 

 

원리는 비슷하나 책에서는 조금 더 신박한 방법을 제시한다.

역직렬화 시, 빠른 런너와 같은 방식으로 왼쪽, 오른쪽 자식 노드가 각각 별도의 인덱스를 부여 받아 각각 탐색해 나간다.

비어있는 노드의 경우 직렬화 때는 '#'으로 표기하고, 역직렬화 때는 값으로 '#'을 가지고 있으면 큐에 삽입하지 않도록 하여 처리를 한다.

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('#')  # null 처리

        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()
            # 왼쪽 자식 노드가 null이 아닌 경우
            if nodes[index] is not '#':
                node.left = TreeNode(int(nodes[index]))
                queue.append(node.left)
            index += 1

            # 오른쪽 자식 노드가 null이 아닌 경우
            if nodes[index] is not '#':
                node.right = TreeNode(int(nodes[index]))
                queue.append(node.right)
            index += 1

        return root

 

 

파이썬 알고리즘 인터뷰 - 교보문고