Subtree of Another Tree

LC 572

• 類別：DFS / Tree Comparison
• 判斷樹 t 是否是樹 s 的子樹。
• （即存在一個節點 x，使得以 x 為根的子樹與 t 完全相同）

thoughts

• 遍歷 s 的每個節點。
• 當找到與 t 根節點值相同的節點時，用 isSameTree() 判斷是否相同。
• 時間：O(m * n)（最壞情況，m 與 n 為樹的節點數）
• 空間：O(h)
• 可優化版本（進階 Follow-up）：
  • 先將樹序列化為字串（例如 preorder），再用 KMP 或 Rabin-Karp 檢查子字串。
    → 時間可降為 O(m + n)

Kotlin

fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
    if (root == null) return false
    if (isSameTree(root, subRoot)) return true
    return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot)
}

fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
    if (p == null && q == null) return true
    if (p == null || q == null) return false
    if (p.`val` != q.`val`) return false
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)
}

Follow-up

• 如何用序列化 + 字串比對優化時間？
• 若樹節點數非常大，如何減少遞迴堆疊？
• 如何處理多棵子樹同時比對（批次匹配）？