給定兩棵二元樹 root 和 subRoot，判斷 root 中是否存在一棵子樹，與 subRoot 結構和值完全相同。
Example:
Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true
Intuition
TIP
對 root 的每個節點檢查：以它為根的子樹是否和 subRoot 相同。
- 結合「遍歷每個節點」和「判斷兩棵樹是否相同」（Same Tree）
- 也可以序列化兩棵樹再用字串匹配
Approaches
⭐ 1. Recursive DFS + Same Tree — O(m * n) / O(h)
- Idea: 對 root 的每個節點呼叫
isSameTree，若任一匹配成功則回傳 true - Time:
O(m * n)，m 和 n 分別為兩棵樹的節點數 - Space:
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. Serialize + String Match — O(m + n) / O(m + n)
- Idea: 將兩棵樹序列化為字串，用字串匹配判斷 subRoot 的序列化是否為 root 序列化的子字串
- Time:
O(m + n)（使用 KMP 或內建字串搜尋） - Space:
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)}"
}
}Watch Out: Serialization Pitfall
序列化時需要加分隔符（如逗號）避免數值混淆。例如 12 和 1,2 不同。
使用前綴逗號 ,val 的格式可以確保每個節點值被明確界定。
🔑 Takeaways
- Pattern: 子樹問題 = 遍歷 + Same Tree 檢查
- Key trick: 善用已解決的子問題（Same Tree）來組合更複雜的問題