[LeetCode] 297. Serialize and Deserialize Binary Tree [Python(파이썬)]

'파이썬 알고리즘 인터뷰'를 보고 작성한 글입니다. 😀

문제 👉 <Serialize and Deserialize Binary Tree - LeetCode>

1. 문제 (이진 트리 직렬화 & 역직렬화)

이진 트리를 배열로 직렬화하고, 반대로 역직렬화하는 기능을 구현하라.

다음과 같은 트리는 [1, 2, 3, null, null, 4, 5] 형태로 직렬화할 수 있다.

2. 풀이

BFS를 이용한 풀이

3. 코드

# 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
        """

        q = collections.deque([root])
        result = []

        while q:
            node = q.popleft()
            if node:
                q.append(node.left)
                q.append(node.right)
                result.append(str(node.val))
            else:
                result.append('#') # null을 '#'으로 표현

        return ' '.join(result)



    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """

        if data == '#': return None

        nodes = data.split()

        root = TreeNode(int(nodes[0]))
        q = collections.deque([root])
        idx = 1

        while q:
            node = q.popleft()
            if nodes[idx] != '#':
                node.left = TreeNode(int(nodes[idx]))
                q.append(node.left)
            idx += 1

            if nodes[idx] != '#':
                node.right = TreeNode(int(nodes[idx]))
                q.append(node.right)
            idx += 1

        return root






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

• 결과 :

방식	Status	Runtime	Memory	Language
BFS	[Accepted]	221 ms	18.8 MB	python3

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋