297. Serialize and Deserialize Binary Tree

Hard
Description

設計一個演算法來序列化和反序列化二元樹。序列化是將樹轉換為字串，反序列化是將字串還原為原始樹結構。不限定格式，只要能正確還原即可。

Example:

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

Intuition#

使用前序遍歷序列化（null 用特殊標記），反序列化時按相同順序重建。

  • 前序遍歷（含 null 標記）可以唯一確定一棵二元樹
  • BFS 層序遍歷也可以，與 LeetCode 自身的格式類似
  • 關鍵是 null 節點也要序列化，否則無法區分不同的樹結構

Approaches#

⭐ 1: Preorder DFS#

  • 概念: 前序遍歷序列化，遇 null 寫 “N”，反序列化時用索引指標依序重建
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Codec() {
    fun serialize(root: TreeNode?): String {
        val sb = StringBuilder()
        fun dfs(node: TreeNode?) {
            if (node == null) {
                sb.append("N,")
                return
            }
            sb.append("${node.`val`},")
            dfs(node.left)
            dfs(node.right)
        }
        dfs(root)
        return sb.toString()
    }

    fun deserialize(data: String): TreeNode? {
        val tokens = data.split(",").toMutableList()
        var idx = 0
        fun dfs(): TreeNode? {
            if (idx >= tokens.size || tokens[idx] == "N" || tokens[idx].isEmpty()) {
                idx++
                return null
            }
            val node = TreeNode(tokens[idx].toInt())
            idx++
            node.left = dfs()
            node.right = dfs()
            return node
        }
        return dfs()
    }
}

2: BFS（層序遍歷）#

  • 概念: 使用佇列進行層序遍歷序列化，反序列化時同樣用佇列逐層重建
  • 時間複雜度: O(n)
  • 空間複雜度: O(n)
class Codec() {
    fun serialize(root: TreeNode?): String {
        if (root == null) return "N"
        val sb = StringBuilder()
        val queue: ArrayDeque<TreeNode?> = ArrayDeque()
        queue.add(root)
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            if (node == null) {
                sb.append("N,")
            } else {
                sb.append("${node.`val`},")
                queue.add(node.left)
                queue.add(node.right)
            }
        }
        return sb.toString()
    }

    fun deserialize(data: String): TreeNode? {
        val tokens = data.split(",")
        if (tokens[0] == "N") return null
        val root = TreeNode(tokens[0].toInt())
        val queue: ArrayDeque<TreeNode> = ArrayDeque()
        queue.add(root)
        var i = 1
        while (queue.isNotEmpty() && i < tokens.size) {
            val node = queue.removeFirst()
            if (i < tokens.size && tokens[i] != "N" && tokens[i].isNotEmpty()) {
                node.left = TreeNode(tokens[i].toInt())
                queue.add(node.left!!)
            }
            i++
            if (i < tokens.size && tokens[i] != "N" && tokens[i].isNotEmpty()) {
                node.right = TreeNode(tokens[i].toInt())
                queue.add(node.right!!)
            }
            i++
        }
        return root
    }
}
為什麼前序遍歷加上 null 標記就能唯一確定一棵樹？

一般來說，單純的前序遍歷無法唯一確定一棵樹（如 [1,2] 的前序可能對應多種結構）。但加上 null 標記後，每個節點的左右子樹邊界就被明確定義了。

例如 1,2,N,N,3,N,N 只能還原為：

    1
   / \
  2   3

因為 2 後面兩個 N 表示 2 沒有子節點，3 後面兩個 N 表示 3 沒有子節點。

🔑 Takeaways#

  • Pattern: 序列化/反序列化 = 選擇遍歷方式 + null 標記 + 對稱的重建邏輯
  • 關鍵技巧: null 標記是讓單一遍歷序列能唯一確定樹結構的關鍵