給定一棵二元樹的根節點，找出所有重複的子樹。兩棵子樹重複意味著它們擁有相同的結構和節點值。對每種重複的子樹，只需回傳其中一棵的根節點。
Example:
Input: root = [1,2,3,4,null,2,4,null,null,4] Output: [[2,4],[4]] (子樹 [2,4] 和子樹 [4] 各出現了兩次)
Intuition
TIP
將每棵子樹序列化為字串，用 HashMap 記錄出現次數，出現第二次時加入結果。
- 要判斷子樹是否相同，最直接的方式是將子樹序列化成唯一的字串表示
- 用 HashMap 記錄每種序列化字串出現的次數
- 當某個序列化字串第二次出現時，將該子樹的根加入結果
Approaches
1. Serialize + HashMap — O(n^2) / O(n^2)
- Idea: 後序遍歷，將每棵子樹序列化為字串，用 HashMap 計數
- Time:
O(n^2)，每個節點的序列化字串長度可達 O(n) - Space:
O(n^2)，存放所有序列化字串
class Solution {
fun findDuplicateSubtrees(root: TreeNode?): List<TreeNode?> {
val result = mutableListOf<TreeNode?>()
val map = HashMap<String, Int>()
fun serialize(node: TreeNode?): String {
if (node == null) return "#"
val s = "${node.`val`},${serialize(node.left)},${serialize(node.right)}"
map[s] = (map[s] ?: 0) + 1
if (map[s] == 2) result.add(node)
return s
}
serialize(root)
return result
}
}⭐ 2. Serialize + ID Mapping — O(n) / O(n)
- Idea: 為每種子樹結構分配唯一 ID（整數），避免重複拼接長字串
- Time:
O(n)，每個節點只做 O(1) 的 triple 比較和 ID 查找 - Space:
O(n)
class Solution {
fun findDuplicateSubtrees(root: TreeNode?): List<TreeNode?> {
val result = mutableListOf<TreeNode?>()
val tripleToId = HashMap<Triple<Int, Int, Int>, Int>()
val idCount = HashMap<Int, Int>()
var nextId = 1
fun dfs(node: TreeNode?): Int {
if (node == null) return 0
val leftId = dfs(node.left)
val rightId = dfs(node.right)
val triple = Triple(node.`val`, leftId, rightId)
val id = tripleToId.getOrPut(triple) { nextId++ }
idCount[id] = (idCount[id] ?: 0) + 1
if (idCount[id] == 2) result.add(node)
return id
}
dfs(root)
return result
}
}🔑 Takeaways
- Pattern: 子樹序列化 — 將樹結構轉換為可比較的表示形式
- Key trick: 用 ID 映射取代字串拼接可以將時間複雜度從 O(n^2) 降到 O(n)，核心思路是為每種子樹結構分配唯一整數 ID