解題說明
Find Duplicate Subtrees
題目描述：給定一棵二元樹的根節點，找出所有重複的子樹。兩棵子樹重複是指它們具有相同的結構和節點值。對於每種重複的子樹，只需回傳其中一棵的根節點。
解題思路：使用後序遍歷對每個子樹進行序列化，將其轉換為唯一的字串表示。用雜湊表記錄每個序列化字串出現的次數：
- 對每個節點，遞迴地序列化其左右子樹。
- 將當前節點的序列化結果組合為
"val,left,right"的形式。 - 若某個序列化字串第二次出現，將該節點加入結果。
為了優化字串比較開銷，可以用整數 ID 替代完整序列化字串。
C++ 解法
複雜度分析
時間複雜度：O(n^2) — 每個節點的序列化字串長度可達 O(n)，共 n 個節點。使用整數 ID 優化可降至 O(n)。
空間複雜度：O(n^2) — 雜湊表儲存所有序列化字串，總長度可達 O(n^2)。使用 ID 優化後為 O(n)。
虛擬碼
1. Create hash map: serialized_string -> count 2. Create result list 3. Define serialize(node): a. If node is null, return "#" b. left_serial = serialize(node.left) c. right_serial = serialize(node.right) d. key = node.val + "," + left_serial + "," + right_serial e. Increment count[key] f. If count[key] == 2, add node to result g. Return key 4. Call serialize(root) 5. Return result
其他解法
整數 ID 優化：用三元組 (val, left_id, right_id) 對映到唯一整數 ID，避免字串拼接和比較的開銷。時間與空間複雜度都降至 O(n)。這是面試中的進階優化方向。
雜湊值法：對子樹計算雜湊值，但需要處理雜湊衝突。實作較複雜，不如 ID 映射法直觀。
延伸思考
- 如何用整數 ID 取代字串序列化來優化到 O(n) 時間？
- 如果只需要找出出現次數最多的重複子樹，該如何修改？
- 這個問題和「判斷兩棵樹是否相同」有什麼關聯？能否復用邏輯？