BST 직렬화 및 역직렬화

직렬화는 파일이나 메모리 버퍼에 저장하거나 네트워크 연결 링크를 통해 전송하여 나중에 동일하거나 다른 컴퓨터 환경에서 재구성할 수 있도록 데이터 구조나 개체를 일련의 비트로 변환하는 것입니다.

이진 검색 트리를 직렬화 및 역직렬화하는 알고리즘을 설계합니다. 직렬화/역직렬화 알고리즘이 작동하는 방식에는 제한이 없습니다. 이진 검색 트리를 문자열로 직렬화할 수 있고 이 문자열을 원래 트리 구조로 역직렬화할 수 있는지 확인해야 합니다.

인코딩된 문자열은 가능한 한 간결해야 합니다.

예 1:

입력: 루트 = [2,1,3]
출력: [2,1,3]

예 2:

입력: 루트 = []
출력: []

제약:

트리의 노드 수가 [0, 104] 범위에 있습니다.

0 <= Node.val <= 104

입력 트리는 이진 검색 트리임이 보장됩니다.

해결책:

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

class Codec:

    def serialize(self, root: Optional[TreeNode]) -> str:
        tree = {}
        paths = [(root, 0)]
        while len(paths) > 0:
            curr, i = paths.pop()
            if curr:
                tree[i] = curr.val
                paths.append((curr.left, 2 * i + 1))
                paths.append((curr.right, 2 * i + 2))
        return ";".join(["{}={}".format(k, v) for k, v in tree.items()])

    def deserialize(self, data: str) -> Optional[TreeNode]:
        vals = data.split(";")
        tree = {}
        for v in vals:
            if len(v) > 0:
                key, value = v.split("=")
                tree[int(key)] = int(value)
        if len(tree) == 0:
            return None
        root = TreeNode()
        paths = [(root, 0)]
        while len(paths) > 0:
            curr, i = paths.pop()
            curr.val = tree[i]
            if (2 * i + 1) in tree:
                curr.left = TreeNode()
                paths.append((curr.left, 2 * i + 1))
            if (2 * i + 2) in tree:
                curr.right = TreeNode()
                paths.append((curr.right, 2 * i + 2))
        return root

# Your Codec object will be instantiated and called as such:
# Your Codec object will be instantiated and called as such:
# ser = Codec()
# deser = Codec()
# tree = ser.serialize(root)
# ans = deser.deserialize(tree)
# return ans