Serialize and Deserialize Binary Tree (Tree)

LC 297 題意

• 設計演算法將一棵二元樹「序列化（Serialize）」為字串，並能再從該字串「反序列化（Deserialize）」回原本的樹。
• 要求：可以正確保留樹的結構與空節點資訊。
• Ex.
  Input: [1,2,3,null,null,4,5]
  Output: same structure after serialization & deserialization

thoughts

核心概念: 前序遍歷 + Null 標記

• 使用前序遍歷將節點序列化。
• 節點為 null 時記錄 "null"。
• 使用分隔符（如 ,）分開。
• 反序列化時，根據前序順序遞迴重建。

Kotlin

class TreeNode(var `val`: Int) {
    var left: TreeNode? = null
    var right: TreeNode? = null
}

class Codec {
    // Encodes a tree to a single string.
    fun serialize(root: TreeNode?): String {
        val sb = StringBuilder()
        fun dfs(node: TreeNode?) {
            if (node == null) {
                sb.append("null,")
                return
            }
            sb.append("${node.`val`},")
            dfs(node.left)
            dfs(node.right)
        }
        dfs(root)
        return sb.toString()
    }

    // Decodes your encoded data to tree.
    fun deserialize(data: String): TreeNode? {
        val nodes = ArrayDeque(data.split(","))
        fun dfs(): TreeNode? {
            val value = nodes.removeFirst()
            if (value == "null" || value.isEmpty()) return null
            val node = TreeNode(value.toInt())
            node.left = dfs()
            node.right = dfs()
            return node
        }
        return dfs()
    }
}

Follow-up

• 如果樹非常大（>10⁶ 節點），如何避免 stack overflow？
  • → 改為 BFS 層序遍歷序列化。
• 是否能以更高壓縮率表示？
  • → 可轉為 array representation 或 bit encoding。
• 若是 N-ary tree，如何序列化？
  • → 額外記錄每個節點的 children 數量。