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

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

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

출처 : 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

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

퍼센테이지가 이뻐서 박제

from http://pythaac.tistory.com/117 by ccl(A) rewrite - 2021-08-03 23:26:56