652. Find Duplicate Subtrees

Medium

Description

給定一棵二元樹的根節點，找出所有重複的子樹。兩棵子樹重複意味著它們擁有相同的結構和節點值。對每種重複的子樹，只需回傳其中一棵的根節點。

Example:

Input: root = [1,2,3,4,null,2,4,null,null,4] Output: [[2,4],[4]] (子樹 [2,4] 和子樹 [4] 各出現了兩次)

Intuition#

將每棵子樹序列化為字串，用 HashMap 記錄出現次數，出現第二次時加入結果。

要判斷子樹是否相同，最直接的方式是將子樹序列化成唯一的字串表示
用 HashMap 記錄每種序列化字串出現的次數
當某個序列化字串第二次出現時，將該子樹的根加入結果

Approaches#

1: 序列化 + HashMap#

概念: 後序遍歷，將每棵子樹序列化為字串，用 HashMap 計數
時間複雜度: O(n^2)，每個節點的序列化字串長度可達 O(n)
空間複雜度: 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: 序列化 + ID 映射優化#

概念: 為每種子樹結構分配唯一 ID（整數），避免重複拼接長字串
時間複雜度: O(n)，每個節點只做 O(1) 的 triple 比較和 ID 查找
空間複雜度: 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: 子樹序列化 — 將樹結構轉換為可比較的表示形式
關鍵技巧: 用 ID 映射取代字串拼接可以將時間複雜度從 O(n^2) 降到 O(n)，核心思路是為每種子樹結構分配唯一整數 ID