(LeetCode) 297. Serialize and Deserialize Binary Tree

297. Serialize and Deserialize Binary Tree

• Explore : Interview > Top Interveiw Questions > Medium Collection
• 분류 : Design
• 난이도 : Medium

Problem

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.

Example 1

Input: root = [1,2,3,null,null,4,5]
Output: [1,2,3,null,null,4,5]

Example 2

Input: root = []
Output: []

Example 3

Input: root = [1]
Output: [1]

Example 4

Input: root = [1,2]
Output: [1,2]

Constraints

• The number of nodes in the tree is in the range [0, 10^4].
• -1000 <= Node.val <= 1000

Solution

Exapnder

/**
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */

class Codec() {
	// Encodes a URL to a shortened URL.
    fun serialize(root: TreeNode?): String {
        return if (root == null) {
            ""
        } else {
            listOf(root.`val`, serialize(root.left), serialize(root.right)).joinToString(",")
        }
    }
    
    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? {
        return deserialize(data.split(",").toMutableList())
    }
    
    private fun deserialize(nodes: MutableList<String>): TreeNode? {
        var head = nodes.removeAt(0)
        if (head == null || head == "") {
            return null
        }
        val node = TreeNode(head.toInt())
        if (nodes.isNotEmpty()) {
            node.left = deserialize(nodes)
            node.right = deserialize(nodes)
        }
        return node
    }
}

/**
 * Your Codec object will be instantiated and called as such:
 * var ser = Codec()
 * var deser = Codec()
 * var data = ser.serialize(longUrl)
 * var ans = deser.deserialize(data)
 */

Point of Thinking

• 이진 트리의 순회 방법을 정한 뒤, 재귀를 통해 String으로 만들면서 구분자를 부여하여 직렬화한다.
• 역직렬화시 구분자로 split하여 리스트로 만든 후 동일하게 복구한다.
• removeFirst()와 removeFirstOrNull()을 leetcode 에서는 쓸 수 없다.