47. Serialize and Deserialize Binary Tree

리트코드

• 이진 트리를 배열로 직렬화하고, 반대로 역직렬화하는 기능을 구현하라.
  즉 다음과 같은 트리는 [1,2,3,null,null,4,5] 형태로 직렬화할 수 있을 것이다.

1. 직렬화 & 역직렬화 구현

# 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: TreeNode) -> str:
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        
        queue = collections.deque([root])
        result = ['#']
        
        #트리 BFS 직렬화
        while queue:
            node = queue.popleft()
            if node:
                queue.append(node.left)
                queue.append(node.right)
                
                result.append(str(node.val))
                
            else:
                result.append('#')
                
        return ' '.join(result)
        

    def deserialize(self, data: str) -> TreeNode:
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        
        #예외 처리
        if data == '# #':
            return None
        
        nodes = data.split()
        
        root = TreeNode(int(nodes[1]))
        queue = collections.deque([root])
        index = 2
        
        #빠른 런너처럼 자식 노드 결과를 먼저 확인 후 큐 삽입
        while queue:
            node = queue.popleft()
            if nodes[index] is not '#':
                node.left = TreeNode(int(nodes[index]))
                queue.append(node.left)
            index += 1
            
            if nodes[index] is not '#':
                node.right = TreeNode(int(nodes[index]))
                queue.append(node.right)
            index += 1
            
        return root
        

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

직렬화 & 역직렬화

• 직렬화를 제대로 구현하기 위해서는 우선 이진 트리의 특징과 표현(Representation)에 대해 정확히 알아야 한다.

  • '이진 트리' 데이터 구조는 논리적인 구조다.

• 이를 파일이나 디스크에 저장하기 위해서는 물리적인 형태로 바꿔줘야 하는데, 이를 직렬화(Serialize)라고 한다.

  • 반대는 역직렬화(Deserialize)이다.

• 파이썬에서는 pickle이라는 직렬화 모듈을 기본으로 제공한다.

  • 이 모듈의 이름으로 인해 파이썬 객체의 계층(Hierarchy) 구조를 바이트 스트림(Byte Stream)으로 변경하는 작업을 피클링(Pickling)이라고도 한다.

    • 마샬링(Marshalling), 플래트닝(Flattening) 등으로 표현하기도 한다.

  
  
  

<이진 힙의 배열 표현>

• 그림 1) 이진 힙은 완전 이진 트리(Complete Binary Tree)로서, 배열로 표현하기 매우 좋은 구조다. 높이 순서대로 순회하면 모든 노드를 배열에 낭비 없이 배치할 수 있기 때문이다.

  • 그림 2)처럼 완전 이진 트리는 배열에 빈틈없이 배치가 가능하다.

  • 트리의 배열 표현의 경우 계산을 편하게 하기 위해 인덱스는 1부터 사용한다.

• 해당 노드의 인덱스를 알면 깊이가 얼마인지, 부모와 자식 노드가 배열 어디에 위치하는지 바로 알아낼 수 있다.

  • 깊이는 1, 2, 4, 8 ... 순으로 2배씩 증가한다.

  • 인덱스는 1부터 시작했기 때문에 부모/자식 노드의 위치는 각각 다음과 같이 계산할 수 있다.

    • 부모: 내림 i/2

    • 왼쪽 자식: 2i

    • 오른쪽 자식 2i + 1

  
  

직렬화

• 이 문제는 직렬화 알고리즘에 제약이 없으므로 BFS, DFS 둘 다 상관이 없다.

  • BFS 탐색 결과로 표현해서, 배열만 봐도 트리의 형태를 직관적으로 떠올릴 수 있도록 이해하기 쉽게 구현해보자.

<이진 트리의 BFS 탐색 결과 표현>

• 이진트리를 BFS로 표현하면 순서대로 배치되기 때문에, DFS에 비해 매우 직관적으로 알아볼 수 있다.

• 그림 2)에 제시한 배열과 동일한 형태가 된다.

  • 여기서 파란 글씨는 인덱스며, 회색 글씨는 비어 있는 인덱스를 의미한다.

• 그림 1)에서 트리는 비어 있는 노드들은 마찬가지로 그림 2) 배열에서도 공간을 비워 두었는데, 여기서는 널(Null) 대신 코드에서는 #으로 표현 하기로 한다.

  • 이 문제의 경우 리턴 값을 문자열로 받게 했는데, 파이썬의 널인 None은 문자열로 만들 수 없기 때문이다.

  • 따라서, 0번 인덱스와 4, 5번은 모두 #으로 표현한다.

• 먼저 앞서 45번 '이진 트리 반전' 문제에서 풀이했던 BFS 반복 풀이를 그대로 가져온다.

  • 함수 이름을 먼저 변경한다.

  • 여기서는 스왑을 사용할 일이 없으므로 필요가 없으니 코드와 주석을 모두 제거한다.

  • 이 함수는 리턴 타입이 문자열인 만큼 리턴에 사용할 변수를 별도로 설정한다.

  • BFS 코드의 뼈대가 갖춰졌다.

def serialize(self, root: TreeNode) -> str:
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        
        queue = collections.deque([root])
        result = ['#']
        
        #트리 BFS 직렬화
        while queue:
            node = queue.popleft()
            if node:
                queue.append(node.left)
                queue.append(node.right)
                
               ...
                
        return ' '.join(result)

• ...부분에 result 변수를 처리할 비즈니스 로직을 구현해준다면 구현이 모두 끝날 것이다.

  • result에는 현재 노드의 값을 추가했다. 이렇게 하면 큐에는 BFS 탐색 결과가 계속 추가 되면서 마지막 노드까지 차례대로 배열로 표현될 것이다.

    • 노드가 존재하지 않을 경우, 널이라는 의미로 #을 추가한다.

  • 마지막으로 result는 리스트가 아닌 배열로 바꿔준다.

    return ' '.join(result)

역직렬화

• 동일하게 큐를 이용해 역직렬화를 진행한다.

• split()으로 공백 단위로 문자열을 끊어서 nodes라는 리스트 변수로 만든다.

• 다음으로 트리로 만들어 줄 노드 변수 root 부터 셋팅하고 큐 변수도 만들어 준다.

• 이제 큐를 순회하면서 처리하면 되는데, 왼쪽 자식과 오른쪽 자식은 각각 별도의 인덱스를 부여받아 다음과 같이 nodes를 먼저 탐색해 나간다.

  • 마치 런너 기법에서 빠른 런너가 먼저 노드를 탐색해 나가는 것고 유사하다.

  • #인 경우에는 큐에 삽입하지 않고, 아무런 처리도 하지 않는다.

    • # A B C # # D E # # # #은 E 이후에 더 이상 큐에 삽입되지 않으며, 빠른 런너처럼 훨씬 더 앞의#은 읽어들이긴 하지만 노드의 값이 #의므로 아무런 처리도 하지 않을 것이다.

  • 이렇게 끝까지 순회하고 나면 원래의 트리 구조로 복원된다.