Serialize and Deserialize BST

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 search tree.
There is no restriction on how your serialization/deserialization algorithm should work.
You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

코드 (Ruby)

def serialize(root)
    if root == nil
        return 'X'
    end

    left = serialize(root.left)
    right = serialize(root.right)

    return "#{root.val} #{left} #{right}"
end

def deserialize(data)
    tokens = data.split(' ')
    deserialize_helper tokens
end

def deserialize_helper(data)
    curr = data.shift

    if curr == 'X'
        return nil
    end

    root = TreeNode.new(curr)
    root.left = deserialize_helper(data)
    root.right = deserialize_helper(data)

    return root
end

설명

preorder 순회 방법을 사용한다.

#6-7에서 root의 왼쪽과 오른쪽 자식의 노드를 찾기 위해 함수를 재귀적으로 호출하고 있다. <br>
nil에 도달할 경우 필자가 임의로 정한 X라는 문자열을 nil대신 반환한다(#2-4; 추후에 디코딩 과정에서 사용). 그리고 마지막으로 문자화한 문자열을 반환한다(#9).

1     def serialize(root)
2         if root == nil
3             return 'X'
4         end
5    
6         left = serialize(root.left)
7         right = serialize(root.right)
8    
9         return "#{root.val} #{left} #{right}"
10    end

data는 문자열 포맷이다.
문자열에서 각 노드들을 분리하고(#2) 이를 helper 함수를 사용해 트리를 재구성한다(#3).

1     def deserialize(data)
2         tokens = data.split(' ')
3         deserialize_helper tokens
4     end

data.shift를 이용해 배열의 첫 번째 값을 가져온 다음 배열에서 지운다(#2).

nil을 의미하는 문자 X를 만날경우 현 노드의 왼쪽 또는 오른쪽 자식이 nil 노드라는 의미가 된다(#4-6).
X가 아닐 경우, 그 값으로 새로운 노르들 만들고 다시 왼쪽과 오른쪽 자식의 값을 재귀적으로 찾는다(#8-10).

연산이 끝났으면 root노드를 반환한다.

1     def deserialize_helper(data)
2         curr = data.shift
3    
4         if curr == 'X'
5             return nil
6         end
7   
8         root = TreeNode.new(curr)
9         root.left = deserialize_helper(data)
10        root.right = deserialize_helper(data)
11   
12        return root
13     end

시간복잡도는 모든 인코딩 과정에서 모든 노드를 한 번씩 방문하기 때문에 O(n)이 된다.
공간복잡도는 재귀함수가 돌때마다 스택 프레임의 크기를 증가시키기 때문에 이 역시 O(n)이 된다.

관련 글


Blog: https://muicode.github.io
Leetcode GitHub: https://github.com/muicode/Leetcode