Medium

449. Serialize and Deserialize BST

stringtreedepth-first-searchbreadth-first-searchdesignbinary-search-treebinary-tree

解題說明

Serialize and Deserialize BST

題目描述：設計序列化與反序列化演算法，將一棵二元搜尋樹（BST）轉換為字串，並能從字串還原為原始的 BST。

解題思路：利用 BST 的性質——前序遍歷序列足以唯一確定一棵 BST（不需要中序遍歷）。序列化時進行前序遍歷，將每個節點值轉為字串。反序列化時，利用值域上下界遞迴重建：讀取下一個值，若在 [minVal, maxVal] 範圍內就建立節點，否則回傳 null。這比通用的二元樹序列化更緊湊，因為不需要記錄 null 節點。

C++ 解法

複雜度分析

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

空間複雜度：O(n) — 序列化字串佔 O(n)；遞迴堆疊在最壞情況下佔 O(n)（偏斜樹），平均 O(log n)。

虛擬碼

1. Serialize(root):
   a. Preorder traversal: append "val " for each node
   b. Return the resulting string
2. Deserialize(data):
   a. Maintain a position pointer pos = 0
   b. Call desHelper(data, pos, INT_MIN, INT_MAX)
3. desHelper(data, pos, minVal, maxVal):
   a. If pos >= data.length, return null
   b. Parse next integer val from data at pos
   c. If val not in [minVal, maxVal], return null (don't advance pos)
   d. Advance pos past the parsed value
   e. Create node with val
   f. node.left = desHelper(data, pos, minVal, val)
   g. node.right = desHelper(data, pos, val, maxVal)
   h. Return node

其他解法

BFS 層序遍歷：用佇列進行層序遍歷序列化（包含 null 標記），反序列化時同樣用佇列重建。適用於通用二元樹但對 BST 而言序列化字串會較長（包含大量 null 標記）。

後序遍歷 + 值域重建：與前序遍歷類似的思路，用後序遍歷序列化，反序列化時從右到左讀取，先建右子樹再建左子樹。等價方法，只是遍歷順序不同。

延伸思考

如果 BST 允許重複值，前序遍歷還能唯一確定樹的結構嗎？需要額外什麼資訊？
如何用二進位格式序列化以減少字串長度？（提示：每個 int 固定 4 bytes）
此方法與 LeetCode 297（通用二元樹序列化）的方法相比，在空間效率上有何差異？

解題說明

Serialize and Deserialize BST

題目描述：設計序列化與反序列化演算法，將一棵二元搜尋樹（BST）轉換為字串，並能從字串還原為原始的 BST。

虛擬碼

1. Serialize(root): a. Preorder traversal: append "val " for each node b. Return the resulting string 2. Deserialize(data): a. Maintain a position pointer pos = 0 b. Call desHelper(data, pos, INT_MIN, INT_MAX) 3. desHelper(data, pos, minVal, maxVal): a. If pos >= data.length, return null b. Parse next integer val from data at pos c. If val not in [minVal, maxVal], return null (don't advance pos) d. Advance pos past the parsed value e. Create node with val f. node.left = desHelper(data, pos, minVal, val) g. node.right = desHelper(data, pos, val, maxVal) h. Return node

其他解法

延伸思考

如果 BST 允許重複值，前序遍歷還能唯一確定樹的結構嗎？需要額外什麼資訊？
如何用二進位格式序列化以減少字串長度？（提示：每個 int 固定 4 bytes）
此方法與 LeetCode 297（通用二元樹序列化）的方法相比，在空間效率上有何差異？