100. Same Tree

Easy

Description

給定兩棵二元樹的根節點 p 和 q，判斷它們是否結構相同且對應節點值相等。

Example:

Input: p = [1,2,3], q = [1,2,3] Output: true

Intuition#

兩棵樹相同 = 根節點值相同 + 左子樹相同 + 右子樹相同。

同時對兩棵樹進行遍歷，比較每個對應位置的節點
Base case：兩個都是 null 則相同；一個是 null 另一個不是則不同

Approaches#

⭐ 1: Recursive DFS#

概念: 遞迴比較兩棵樹的根、左子樹、右子樹
時間複雜度: O(n)，n 為較小樹的節點數
空間複雜度: 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)

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: 同步遍歷兩棵樹 — 比較結構的基礎模式
關鍵技巧: 處理 null 的邊界條件要仔細：先處理「兩個都 null」再處理「一個 null」