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.
굉장히 긴 설명이지만 사실 간단한 내용이다
Serialize는 트리를 String으로 변환하는 함수, Deserialize는 이런 String을 다시 트리로 변환하는 함수
즉 트리가 주어졌을때 String으로 변환해서 String을 Input으로 받을때 다시 트리로 바꾸는 알고리즘을 만드는 문제
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/
Example 1:
Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Example 2:
Input: root = []
Output: []
Leetcode에서 왜 이 문제를 하드로 분류했는지 잘 모르겠다
DFS를 사용하는 순서만 사용하면 이를 배열에 넣어 String으로 바꾸면 된다
이 String을 사용해서 그대로 다시 DFS로 풀이를 하면 원래 트리를 다시 만들어 낼 수 있다
Serialize:
1. Root부터 시작해서 값을 배열에 넣는다
2. 왼쪽 부터 탐색해서 오른쪽까지 끝날때 까지 DFS를 통해 Root 노드를 배열에 추가한다
3. None에 도달했을때 이해하기 쉽게 나는 "N"을 배열에 추가 했다
4. 모든 노드를 확인한 후 Join으로 배열을 한개의 String으로 만들어서 리턴
※ 여기서 나는 각 노드를 "," 으로 Join해서 Deserialize 할때 바로 다시 배열로 만들었다
Deserialize:
1. 받은 String을 ","로 나눠서 배열을 만든다
2. 이를 통해 None에 도달할때까지 왼쪽, 오른쪽 탐색을 통해 계속해서 Node를 만들어 Value를 추가
3. 이런 과정해서 하나씩 추가할때 마다 index variable을 1씩 추가해서 배열이 끝날때 까지 탐색
class Codec:
def serialize(self, root):
ans = []
def dfs(node):
if not node:
ans.append("N")
return
ans.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(ans)
def deserialize(self, data):
arr = data.split(",")
self.index = 0
def dfs():
if arr[self.index] == "N":
self.index += 1
return None
node = TreeNode(int(arr[self.index]))
self.index += 1
node.left = dfs()
node.right = dfs()
return node
return dfs()
