HardRating 1884

297. Serialize and Deserialize Binary Tree

stringtreedepth-first-searchbreadth-first-searchdesignbinary-tree

在 LeetCode 上作答 ↗

解題說明

Serialize and Deserialize Binary Tree

題目描述：設計將二元樹編碼為字串（序列化）和從字串還原二元樹（反序列化）的演算法。

解題思路：前序遍歷序列化：遞迴訪問節點，空節點記錄為 "#"，各值以逗號分隔。反序列化：將字串分割後，遞迴按前序重建樹——每次讀一個值，若為 "#" 回傳 null，否則建立節點後遞迴建左右子樹。

C++ 解法

複雜度分析

時間複雜度：O(n) — 序列化和反序列化各訪問每個節點一次。

空間複雜度：O(n) — 序列化字串大小，加上 O(h) 遞迴棧。

虛擬碼

Serialize (preorder):
1. If null: append '#'
2. Append node.val
3. Recurse left, recurse right

Deserialize:
1. Read next token from stream
2. If '#': return null
3. Create node with value
4. node.left = deserialize(); node.right = deserialize()
5. Return node

其他解法

中序 + 前序重建 O(n) 時間，O(n) 空間：編碼兩種遍歷，反序列化時重建樹 — 等價但傳輸資料量更多。

標記 None 節點 O(n) 時間，O(n) 空間：序列化時直接用字符表示 None（如 #），簡化解析 — 此即本方法。

延伸思考

若樹包含重複值，序列化還唯一嗎？
如何實現緊湊二進制序列化？
若樹非常大，如何流式序列化？

Serialize and Deserialize Binary Tree — CaffeCode