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(通用二元樹序列化)的方法相比,在空間效率上有何差異?