設計一個演算法來序列化和反序列化二元樹。序列化是將樹轉換為字串，反序列化是將字串還原為原始樹結構。不限定格式，只要能正確還原即可。
Example:
Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5]
Intuition
TIP
使用前序遍歷序列化（null 用特殊標記），反序列化時按相同順序重建。
- 前序遍歷（含 null 標記）可以唯一確定一棵二元樹
- BFS 層序遍歷也可以，與 LeetCode 自身的格式類似
- 關鍵是 null 節點也要序列化，否則無法區分不同的樹結構
Approaches
⭐ 1. Preorder DFS — O(n) / O(n)
- Idea: 前序遍歷序列化，遇 null 寫 “N”，反序列化時用索引指標依序重建
- Time:
O(n) - Space:
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 (Level-order) — O(n) / O(n)
- Idea: 使用佇列進行層序遍歷序列化，反序列化時同樣用佇列逐層重建
- Time:
O(n) - Space:
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
}
}Why preorder with null markers uniquely determines a tree?
一般來說，單純的前序遍歷無法唯一確定一棵樹（如 [1,2] 的前序可能對應多種結構）。但加上 null 標記後，每個節點的左右子樹邊界就被明確定義了。
例如 1,2,N,N,3,N,N 只能還原為：
1
/ \
2 3因為 2 後面兩個 N 表示 2 沒有子節點，3 後面兩個 N 表示 3 沒有子節點。
🔑 Takeaways
- Pattern: 序列化/反序列化 = 選擇遍歷方式 + null 標記 + 對稱的重建邏輯
- Key trick: null 標記是讓單一遍歷序列能唯一確定樹結構的關鍵