ch14-6(leetcode 297). 이진 트리 직렬화 & 역직렬화

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 297번 ( https://leetcode.com/problems/serialize-and-deserialize-binary-tree/description/ )

 

✅교재를 참고하지 않은 풀이

 

📌BFS

 

(1) 직렬화

 

직렬화(TreeNode -> string) 로직에서는 root 노드 하나를 입력으로 받아서 그 아래 있는 노드들을 문자열 형식으로 출력해야 한다. 따라서 root 노드에서 시작해서 자식 노드들을 레벨 순서대로 순회해야 한다. 

 

1. 트리 전체의 노드를 데크에 레벨 순서대로 담기

이전 문제에서도 트리 전체를 탐색하는 데 BFS 방법을 사용한 것처럼, 큐(여기서는 데크)를 이용하면 트리의 모든 노드를 레벨 순서대로 순회할 수 있다. 파이썬의 데크 자료형은 리스트와 거의 유사하지만 내부적으로는 투 포인터를 사용해서 구현되었기 때문에 리스트의 맨 앞과 맨 뒤에서 원소를 추가하거나 삭제하는 데 O(1)이 소요된다. 

 

2. 불필요한 null 노드 제거하기

그러나 이대로 리스트로 변환할 수는 없고 추가 작업이 필요하다. 문제의 예시에서는 null인 노드가 있더라도 그 레벨보다 더 낮은 레벨에 노드가 존재하는 경우 'null' 값으로 표시되어야 하기 때문에 데크의 중간중간 null 값이 들어있다. 

 

위 그림의 경우 노드 값만 순서대로 나타내면 [1,2,3,4,5]이지만 중간의 빈 노드도 포함하기 때문에 실제로는 [1,2,3,null,null,4,5]가 리턴되어야 한다. 이렇게 나타내려면 left, right 자식 노드가 전부 null인 '2'번 노드를 탐색할 때도 2번 노드의 자식 노드를 큐에 추가해야 한다. 

 

그러나 이 방법대로 탐색하면 결과는 [1,2,3,null,null,4,5,null,null]로 출력된다. 4, 5번의 자식 노드가 없지만 2번과 같은 방법으로 탐색하여 null인 자식 노드가 큐에 추가되었기 때문이다. 

이를 수정하기 위해서 큐의 맨 뒤의 원소부터 탐색해서, null이 아닌 값이 나올 때까지 지우면 불필요한 null 노드(leaf 노드의 자식 노드)를 제거할 수 있다. 

 

3. 큐를 문자열로 변경

지금까지 작업했던 큐(데크) 형태의 자료형을 문자열로 바꿔서 출력해야 한다. str()로 큐를 문자열 형식으로 바꿔 준 다음, 출력 형식에 맞게 공백을 제거하고 "None"을 "null"로 바꾸는 추가 작업을 해서 바꿔준다. 

 

전체 직렬화 코드는 다음과 같다. 

def serialize(self, root):

    # use bfs
    if not root:
        return "[]"

    queue = collections.deque([root])
    array = []

    while queue:
        for _ in range(len(queue)):
            elem = queue.popleft()
            if elem is None:
                array.append(None)
            else:
                array.append(elem.val)
                queue.append(elem.left)
                queue.append(elem.right)

    while True:
        if array[-1] is None:
            array.pop()
        else:
            break

    result = str(array).replace(" ", "").replace("None", "null")
    return result

 

 

(2) 역직렬화

 

역직렬화(string->TreeNode) 로직에서는 앞서 문자열로 바꾼 값을 변환해서 트리의 모든 값을 left, right 자식 노드로 포함한 root 노드를 리턴해야 한다. 

 

1. 문자열을 리스트(배열)로 변환

앞서 추가 처리를 통해 데크를 문자열로 변환했었는데 이번에는 반대로 작업한다. 문자열의 앞뒤로 붙은 괄호[]를 제거한 뒤 ,로 구분된 원소들을 .split() 메소드를 사용해서 배열로 변환한다. 그러면 트리의 각 노드들의 값이 문자열 형태로 순서대로 저장된 배열을 얻을 수 있다. 

 

위의 트리 노드의 경우 ["1", "2", "3", "null", "null", "4", "5"]의 문자열 값들이 저장된 배열을 얻을 수 있다. 

 

2. 큐를 사용해서 배열의 값들을 추가로 트리 노드에 할당하기

위 배열의 값을 root 노드부터 순서대로(부모->자식 방향으로) 할당해야 한다. 앞서 레벨 순서대로 탐색하기 위해서 큐를 사용했는데, 같은 이유로 여기서도 큐를 사용한다. 

우선 root 노드의 값(1번 배열의 첫 번째 원소)을 가진 트리 노드를 선언한 뒤 해당 노드를 원소로 가진 큐를 선언한다. 트리 노드를 선언하는 데 사용된 배열의 값은 배열에서 제거해 준다. 

 

여기서의 배열은 큐가 아닌 리스트이지만 pop(0) 메소드를 사용하면 맨 앞에서도 원소를 제거할 수 있다. (물론 큐와 달리 O(1)이 아니라 O(n) 만큼의 시간이 걸린다.)

 

2-1. 배열의 값에 따라서 할당 방식을 다르게 하기

1번 배열의 맨 앞에서부터 값을 제거했을 때, 해당 값이 "null"일 수도, 문자열 형식의 숫자일 수도 있다. 

 

null 값이라면 트리 노드를 선언해서 값을 할당하지 않고 None 값을 할당하자.

반면 문자열 형식의 숫자(ex. "1")라면 해당 값을 숫자로 변환한 뒤 이 값을 value로 갖는 트리 노드를 선언해서 연결해 주자. 

 

이때 트리 노드는 위의 레벨에서 아래 레벨로, 왼쪽부터 오른쪽으로 할당되므로 한 노드의 자식 노드에 값을 할당할 때도 왼쪽 자식 노드부터 할당해 준다. 

 

전체 역직렬화 코드는 다음과 같다. 

def deserialize(self, data):

    if data == "[]":
        return None

    string = data.replace("[", "").replace("]", "")
    array = string.split(",")

    root = collections.deque([TreeNode(array.pop(0))])
    head = root[0]

    while root and array:
        elem = root.popleft()
        if elem is not None:
            if array:
                if array[0] == "null":
                    array.pop(0)
                    elem.left = None
                    root.append(None)
                else:
                    elem.left = TreeNode(int(array.pop(0)))
                    root.append(elem.left)
            if array:
                if array[0] == "null":
                    array.pop(0)
                    elem.right = None
                    root.append(None)
                else:
                    elem.right = TreeNode(int(array.pop(0)))
                    root.append(elem.right)

    return head