[파이썬 알고리즘] 20. 이진트리 직렬화 & 역직렬화

 

 

1. 문제 

Leetcode 297. Serialize and Deserialize Binary Tree

 주어진 TreeNode root를 string으로 직렬화시키는 함수 serialize, 다시 TreeNode로 역직렬화시키는 deserialize 함수를 구현하여라.

 

2. serialize 구현

 덱을 이용한 BFS로 탐색한다. root를 넣어 다음에 탐색할 노드들을 넣을 덱을 만들고 덱에 남아있는 노드가 없을 때까지 탐색을 진행한다. 매 탐색 때마다 덱의 왼쪽에서 노드를 하나씩 뺀다. 만약 뺀 노드가 None이 아니라면 node의 값을 result에 추가하고, 자식 노드들을 덱에 추가한다. 탐색이 종료되면 result를 콤마로 구분되는 문자열로 만들어 리턴한다.

 

def serialize(self, root):

    if not root:
        return ''

    # 배열로 옮길 노드 덱
    deque = collections.deque([root])
    result = []

    while deque:
        node = deque.popleft()

        if not node:
            result.append('null')
            continue

        result.append(str(node.val))

        deque.append(node.left)
        deque.append(node.right)


    return ','.join(result)

 

 

3. deserialize 구현

 주어진 문자열을 콤마열을 기준으로 나누어 배열로 만들고, 해당 배열이 없어질 때까지 탐색을 진행한다. 탐색을 진행하기 전 트리에 추가할 노드가 머무는 덱을 만든다. 그리고 root 노드를 만들고 해당 배열에 처음으로 넣어준다. 탐색 과정에서는 사용할 노드를 덱에서 꺼내고, 왼쪽 자식 노드를 만들고 현재 노드와 연결한다. 배열이 끝나지 않았다면 오른쪽 자식 노드를 만들고 현재 노드와 연결한다. 탐색이 끝나면 root 노드를 리턴한다.

def deserialize(self, data):

    if not data:
        return []

    #사용할 모든 값이 저장된 덱
    data = collections.deque(data.split(','))

    #다음에 트리에 추가할 노드가 머무는 덱
    root = TreeNode(data.popleft())
    deque = collections.deque([root])

    while data:
        #사용할 노드 덱에서 꺼내기
        node = deque.popleft()

        #자식 노드 연결하기
        node.left = TreeNode(data.popleft())
        deque.append(node.left)

        if data:
            node.right = TreeNode(data.popleft())
            deque.append(node.right)

    return root

 

4. 배운 점

- 문제가 생기면 정확하게 문제 파악하기