題目描述:給定一棵二元樹的根節點,找出所有重複的子樹。兩棵子樹重複是指它們具有相同的結構和節點值。對於每種重複的子樹,只需回傳其中一棵的根節點。
解題思路:使用後序遍歷對每個子樹進行序列化,將其轉換為唯一的字串表示。用雜湊表記錄每個序列化字串出現的次數:
"val,left,right" 的形式。為了優化字串比較開銷,可以用整數 ID 替代完整序列化字串。
時間複雜度: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 映射法直觀。