297. Serialize and Deserialize Binary Tree
문제 설명
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.
입출력 예시
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
조건
The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000
코드
import math
from collections import deque
class Codec:
def bfs(self,root:Optional[TreeNode],serial:list):
queue=deque()
queue.append(root)
while queue:
node=queue.popleft()
if node:
queue.append(node.left)
queue.append(node.right)
serial.append(node.val)
else:
serial.append('x')
def serialize(self, root:TreeNode)->str:
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if root==None:
return ""
arr=["x"]
self.bfs(root,arr)
serial=""
# arr[0] is just for full bst format. it is not valid data. it should start from [1].
for i in range(len(arr)):
serial+=str(arr[i])
if i!=len(arr)-1:
serial+=','
return serial
def deserialize(self, data)->TreeNode:
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
split=data.split(',')
root=None
if split[0]=='':
return root
root=TreeNode(int(split[1]))
queue=deque([root])
index=2
while queue:
node=queue.popleft()
if index<len(split) and split[index]!='x':
node.left=TreeNode(int(split[index]))
queue.append(node.left)
index+=1
if index<len(split) and split[index]!='x':
node.right=TreeNode(int(split[index]))
queue.append(node.right)
index+=1
return root
해설
import math
from collections import deque
class Codec:
def bfs(self,root:Optional[TreeNode],serial:list):
queue=deque()
queue.append(root)
while queue:
node=queue.popleft()
if node:
queue.append(node.left)
queue.append(node.right)
serial.append(node.val)
else:
serial.append('x')
def serialize(self, root:TreeNode)->str:
"""Encodes a tree to a single string.
:type root: TreeNode
:rtype: str
"""
if root==None:
return ""
arr=["x"]
self.bfs(root,arr)
serial=""
# arr[0] is just for full bst format. it is not valid data. it should start from [1].
for i in range(len(arr)):
serial+=str(arr[i])
if i!=len(arr)-1:
serial+=','
return serial
def deserialize(self, data)->TreeNode:
"""Decodes your encoded data to tree.
:type data: str
:rtype: TreeNode
"""
split=data.split(',')
root=None
if split[0]=='':
return root
root=TreeNode(int(split[1]))
queue=deque([root])
index=2
while queue:
node=queue.popleft()
if index<len(split) and split[index]!='x':
node.left=TreeNode(int(split[index]))
queue.append(node.left)
index+=1
if index<len(split) and split[index]!='x':
node.right=TreeNode(int(split[index]))
queue.append(node.right)
index+=1
return root
이진 트리는 일차원 배열로 변환할 수 있다.
예를 들어, [1,2,3,null,null,4,5]
인 트리라면, ['x',1,2,3,'x','x',4,5]
로 변환할 수 있다. 단, 여기서 배열의 0번째 원소는 사용하지 않는다.
특징으로는 현재 노드가 i번째 원소라면, 왼쪽 자식의 인덱스는 i*2, 오른쪽 자식의 인덱스는 ix2+1이다.
직렬화와 역직렬화 모두 큐를 활용하여 bfs를 실행한다.
링크
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
Author And Source
이 문제에 관하여(297. Serialize and Deserialize Binary Tree), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dasd412/297.-Serialize-and-Deserialize-Binary-Tree저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)