572. Subtree of Another Tree

Easy

Description

給定兩棵二元樹 root 和 subRoot，判斷 root 中是否存在一棵子樹，與 subRoot 結構和值完全相同。

Example:

Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true

Intuition#

對 root 的每個節點檢查：以它為根的子樹是否和 subRoot 相同。

結合「遍歷每個節點」和「判斷兩棵樹是否相同」（Same Tree）
也可以序列化兩棵樹再用字串匹配

Approaches#

⭐ 1: Recursive DFS + Same Tree#

概念: 對 root 的每個節點呼叫 isSameTree，若任一匹配成功則回傳 true
時間複雜度: O(m * n)，m 和 n 分別為兩棵樹的節點數
空間複雜度: O(h)，h 為 root 的高度

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

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

2: 序列化 + 字串匹配#

概念: 將兩棵樹序列化為字串，用字串匹配判斷 subRoot 的序列化是否為 root 序列化的子字串
時間複雜度: O(m + n)（使用 KMP 或內建字串搜尋）
空間複雜度: O(m + n)

class Solution {
    fun isSubtree(root: TreeNode?, subRoot: TreeNode?): Boolean {
        val rootStr = serialize(root)
        val subStr = serialize(subRoot)
        return rootStr.contains(subStr)
    }

    private fun serialize(node: TreeNode?): String {
        if (node == null) return ",#"
        return ",${node.`val`}${serialize(node.left)}${serialize(node.right)}"
    }
}

注意序列化的陷阱

序列化時需要加分隔符（如逗號）避免數值混淆。例如 12 和 1,2 不同。使用前綴逗號 ,val 的格式可以確保每個節點值被明確界定。

🔑 Takeaways#

Pattern: 子樹問題 = 遍歷 + Same Tree 檢查
關鍵技巧: 善用已解決的子問題（Same Tree）來組合更複雜的問題