Leetcode - 297. Serialize and Deserialize Binary Tree
문제
Loading...
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
풀이
얼핏 생각하면 굉장히 쉬워보이는데, 막상 구현해보려고 하면 어렵고, 그림을 그려보면 쉽다.
문제풀이 힌트가 문제 설명에 주어져있다.
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.
트리 문제를 풀면서 리트코드가 어떻게 직렬화를 수행하는지 생각해본 적이 있었는데, 리스트가 트리로 어떻게 바뀌는지 그림을 그려보면 쉽게 이해가 된다.
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if not root:
return None
series = [root.val]
queue = collections.deque([root])
while queue:
node = queue.popleft()
if node.left:
queue.append(node.left)
series.append(node.left.val)
else:
series.append(None)
if node.right:
queue.append(node.right)
series.append(node.right.val)
else:
series.append(None)
idx = len(series)
for i in range(len(series)):
idx -= 1
if series[idx] is not None:
break
return " ".join(map(str, series[: idx + 1]))
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data:
return None
data = data.split(" ")
depth = 0
node = root = TreeNode(int(data.pop(0)))
queue = [node]
while queue and data:
node = queue.pop(0)
if data:
val = data.pop(0)
if val != "None":
node.left = TreeNode(int(val))
queue.append(node.left)
if data:
val = data.pop(0)
if val != "None":
node.right = TreeNode(int(val))
queue.append(node.right)
return root
불필요한 부분을 정리하면 다음과 같다.
class Codec:
def serialize(self, root):
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if not root:
return None
series = []
queue = collections.deque([root])
while queue:
node = queue.popleft()
if node:
queue.append(node.left)
queue.append(node.right)
series.append(node.val)
else:
series.append(None)
return " ".join(map(str, series))
def deserialize(self, data):
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
if not data:
return None
data = data.split(" ")
depth = 0
node = root = TreeNode(int(data.pop(0)))
queue = collections.deque([node])
while queue:
node = queue.popleft()
val = data.pop(0)
if val != "None":
node.left = TreeNode(int(val))
queue.append(node.left)
val = data.pop(0)
if val != "None":
node.right = TreeNode(int(val))
queue.append(node.right)
return root