給定兩棵二元樹的根節點 p 和 q，判斷它們是否結構相同且對應節點值相等。
Example:
Input: p = [1,2,3], q = [1,2,3] Output: true
Intuition
TIP
兩棵樹相同 = 根節點值相同 + 左子樹相同 + 右子樹相同。
- 同時對兩棵樹進行遍歷，比較每個對應位置的節點
- Base case：兩個都是 null 則相同；一個是 null 另一個不是則不同
Approaches
⭐ 1. Recursive DFS — O(n) / O(h)
- Idea: 遞迴比較兩棵樹的根、左子樹、右子樹
- Time:
O(n)，n 為較小樹的節點數 - Space:
O(h)，h 為較小樹的高度
class Solution {
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. Iterative BFS — O(n) / O(n)
- Idea: 使用佇列同時遍歷兩棵樹，逐一比較對應節點
- Time:
O(n) - Space:
O(n)
class Solution {
fun isSameTree(p: TreeNode?, q: TreeNode?): Boolean {
val queue: ArrayDeque<Pair<TreeNode?, TreeNode?>> = ArrayDeque()
queue.add(p to q)
while (queue.isNotEmpty()) {
val (a, b) = queue.removeFirst()
if (a == null && b == null) continue
if (a == null || b == null) return false
if (a.`val` != b.`val`) return false
queue.add(a.left to b.left)
queue.add(a.right to b.right)
}
return true
}
}🔑 Takeaways
- Pattern: 同步遍歷兩棵樹 — 比較結構的基礎模式
- Key trick: 處理 null 的邊界條件要仔細：先處理「兩個都 null」再處理「一個 null」