題目描述:給定兩棵二元樹 root 和 subRoot,判斷 subRoot 是否是 root 的某個子樹(結構和值完全相同)。
解題思路:遞迴:對 root 的每個節點,檢查以它為根的子樹是否與 subRoot 相同(用 isSameTree)。isSubtree(root, subRoot) = isSameTree(root, subRoot) OR isSubtree(root.left, subRoot) OR isSubtree(root.right, subRoot)。
時間複雜度:O(m × n),m、n 分別為兩棵樹的節點數 — 最壞情況每個節點都做 isSameTree。
空間複雜度:O(max(hm, hn)) — 遞迴棧深度。
1. If root is null: return false 2. If isSameTree(root, subRoot): return true 3. Return isSubtree(root.left, subRoot) OR isSubtree(root.right, subRoot)
逐節點檢查 O(m×n) 時間,O(h) 空間:對 s 的每個節點調用 same tree — 時間複雜度相同。
序列化模式匹配 O(m+n) 時間,O(m+n) 空間:序列化兩棵樹,檢查 t 的序列是否為 s 的子串 — 邏輯不同但複雜度相同。