문제 설명

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
                
        
        

해설

이진 트리는 일차원 배열로 변환할 수 있다.
예를 들어, [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/