[DSA][Trees] 15. Serialize and Deserialize Binary Tree

LeetCode 297

 

15. 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.

 

 

[질문하기]

- 노드에 중복된 값이 존재할 수 있나요? YES

 

[아이디어]

- 트리를 BFS 순서로 순회하면서 null 노드는 "N"으로 표시하여 serialize 하고, 다시 같은 순서로 값을 읽어 트리를  deserialize 한다.

 

 

[풀이 1] Breadth First Search

class Codec:
    def serialize(self, root):
        if not root:
            return "N"
        res = []
        queue = deque([root])
        while queue:
            node = queue.popleft()
            if not node:
                res.append("N")
            else:
                res.append(str(node.val))
                queue.append(node.left)
                queue.append(node.right)
        return ",".join(res)
        
    def deserialize(self, data):
        nodes = data.split(",")
        if nodes[0] == "N":
            return None
        root = TreeNode(int(nodes[0]))
        queue = deque([root])
        index = 1
        while queue:
            node = queue.popleft()
            if nodes[index] != "N":
                node.left = TreeNode(int(nodes[index]))
                queue.append(node.left)
            index += 1
            if nodes[index] != "N":
                node.right = TreeNode(int(nodes[index]))
                queue.append(node.right)
            index += 1
        return root

직렬화/복호화를 할 때 DFS를 사용할 수도 있고 BFS를 사용할 수도 있지만, BFS가 더 직관적이라고 생각하여 BFS로 문제를 풀이하였다.
BFS에서는 트리를 레벨 순서대로 탐색하면서 각 노드의 값을 문자열로 이어 붙인다. 만약 노드가 존재하지 않는 경우(None)에는 "N"이라는 문자열을 붙여 null 노드를 명시적으로 표시한다. 이때 항상 왼쪽 → 오른쪽 순서로 자식을 큐에 추가하므로, 트리의 구조를 정확하게 유지할 수 있다. 예를 들어, 노드가 왼쪽 자식만 있고 오른쪽 자식이 없다면 "왼쪽 값,N"처럼 기록되어 트리의 구조가 보존된다.

복원 과정에서는 직렬화된 문자열을 split하여 리스트로 만든 뒤, 첫 번째 값을 루트로 사용한다. 이후 큐를 사용해 BFS 순서로 노드를 처리하면서 "N"이 아닌 경우에만 새로운 노드를 생성하고 자식으로 연결한다. 이때도 마찬가지로 항상 왼쪽 → 오른쪽 순서로 값을 처리하여 직렬화된 순서를 그대로 따라가므로, 원래 트리 구조대로 정확히 복원할 수 있다.

 

추가로, 13. Construct Binary Tree from Preorder and Inorder Traversal에서는 preorder와 inorder 배열을 사용하여 Binary Tree를 복원할 수 있었다. 2025.07.26 - [자료구조와 알고리즘] - [DSA][Trees] 13. Construct Binary Tree from Preorder and Inorder Traversal

그래서 이 문제에서도 serialize에서 preorder, inorder 배열을 각각 문자열로 만들고, deserialize에서 이를 기반으로 트리를 복원하는 아이디어를 생각해 보았다. 하지만 해당 문제에서는 모든 노드의 값이 "unique"하다는 조건이 전제되어 있었기 때문에 가능한 방식이었고, 이 문제에서는 값이 중복될 수 있으므로 사용할 수 없는 방법이다. (preorder + inorder로 이루어진 array를 복원할 때 inorder에서 루트 값의 인덱스를 찾아야 하는데, 같은 값이 여러 개면 정확한 위치를 찾을 수 없기 때문이다.)

 

⏱️ 시간복잡도

트리의 모든 노드를 한 번씩 방문하므로, 시간 복잡도는 O(n)이다.

🧠 공간복잡도

큐에 저장되는 노드의 수가 트리 최대 레벨의 너비에 비례하므로 공간복잡도는 O(n)이다.