[리트코드]297. Serialize and Deserialize Binary Tree

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.

Example 1:

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]
Example 2:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 104].
-1000 <= Node.val <= 1000

풀이

직렬화 : 직렬화는 객체의 내용을 바이트 단위로 변환하여 파일 또는 네트워크를 통해서 스트림(송수신)이 가능하도록 하는 것을 의미(트리 -> 문자열)

역직렬화 : 바이트 또는 json 등 포멧 형태에서 객체로 변환하는 과정(문자열 -> 트리)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """ 

        lst = [] #문자열을 담을 리스트 생성

        def dfs(root): #재귀함수 호출
            if not root: #root가 없으면 list에 "N"문자열 삽입 
                lst.append("N")
                return
            
            lst.append(str(root.val)) #문자열로 만들어야 하기 때.문에 str로 형 변환 후 root.val 값 삽입
            root.left = dfs(root.left) 
            root.right = dfs(root.right)

        dfs(root)
        return ",".join(lst)


    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """

        nodes = data.split(",") // 문자열을 "," 기준으로 분리하여 리스트 생성
        self.i = 0 //전역변수 index값 생성 

        def dfs():
            if nodes[self.i] == "N":
                self.i += 1
                return None
            node = TreeNode(int(nodes[self.i]))
            self.i +=1 
            node.left = dfs()
            node.right = dfs()
            return node
        return dfs()
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# ans = deser.deserialize(ser.serialize(root))