# Problem
Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.
Constraints:
|
# My Answer
class Codec:
def serialize(self, root):
if not root:
return root
result=[]
def bfs(queue):
while queue:
if not queue:
return result
node = queue.pop(0)
if node is None:
result.append("#")
else:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
return result
result = bfs([root])
return result
def deserialize(self, data):
if not data:
return data
root = TreeNode(data.pop(0))
def BFS(queue):
if not queue:
return
if not data:
return
while queue:
node = queue.pop(0)
n = data.pop(0)
if n!="#":
node.left = TreeNode(n)
queue.append(node.left)
else:
node.left = None
n = data.pop(0)
if n!="#":
node.right = TreeNode(n)
queue.append(node.right)
else:
node.right = None
return root
return BFS([root])
# Solution 1 - 직렬화 & 역직렬화 구현
import collections
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) # 문자열 형태로 반환한다 -> deserialize에서 사용
# 역직렬화
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
예제 1번의 트리를 배열로 표시하면
0 1 2 3 4 5 6 7
# A B C # # D E
null 을 '#' 으로 표현
deque 자료형으로 popleft() 사용
인덱스를 하나씩 더해가면서 null이 아닌 경우 현재 노드에 이어붙인다
'Algorithm > LEET CODE ( 파이썬 알고리즘 인터뷰)' 카테고리의 다른 글
[LEET CODE] 108. Convert Sorted Array to Binary Search Tree (0) | 2021.05.19 |
---|---|
❗️[LEET CODE] 310. Minimum Height Trees (0) | 2021.04.20 |
[LEET CODE] 110. Balanced Binary Tree (0) | 2021.04.20 |
[LEET CODE] 617. Merge Two Binary Trees (0) | 2021.04.20 |
[LEET CODE] 226. Invert Binary Tree (0) | 2021.04.20 |