LeetCode中如何解決相同的樹問題

# LeetCode中如何解決相同的樹問題

## 引言

在LeetCode的算法題庫中，"相同的樹"（Same Tree）是一個經典的二叉樹相關問題，通常被標記為簡單難度。該問題要求判斷兩棵二叉樹在結構和節點值上是否完全相同。本文將深入探討該問題的多種解法，包括遞歸法、迭代法，并分析其時間復雜度和空間復雜度，最后提供相應的代碼實現。

---

## 問題描述

**題目編號**：100  
**題目名稱**：相同的樹  
**題目描述**：給定兩棵二叉樹的根節點 `p` 和 `q`，編寫一個函數來檢驗它們是否相同。如果兩棵樹在結構上相同，并且節點具有相同的值，則認為它們是相同的。

**示例 1**：

輸入: p = [1,2,3], q = [1,2,3] 輸出: true

**示例 2**：

輸入: p = [1,2], q = [1,null,2] 輸出: false

---

## 解題思路

### 方法一：遞歸法

遞歸是解決樹問題的常見方法。對于兩棵樹是否相同，可以通過以下步驟判斷：

1. **終止條件**：
   - 如果兩棵樹的當前節點均為 `null`，返回 `true`。
   - 如果一棵樹的當前節點為 `null` 而另一棵不為 `null`，返回 `false`。
   - 如果兩棵樹的當前節點值不同，返回 `false`。

2. **遞歸邏輯**：
   - 分別遞歸比較左子樹和右子樹。

#### 代碼實現（Python）
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not p or not q:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

復雜度分析

• 時間復雜度：O(n)，其中 n 是樹的節點數。每個節點訪問一次。
• 空間復雜度：O(h)，h 是樹的高度。遞歸棧的深度取決于樹的高度。

方法二：迭代法（廣度優先搜索）

遞歸法可能存在棧溢出風險（尤其是樹很深時），因此可以使用迭代法。通過隊列（或棧）實現廣度優先搜索（BFS），逐層比較節點。

算法步驟

1. 初始化隊列，將兩棵樹的根節點入隊。
2. 每次從隊列中取出兩個節點比較：
   • 如果節點值不同，返回 false。
   • 如果左子樹或右子樹結構不一致，返回 false。
3. 將子節點按順序入隊。

代碼實現（Python）

from collections import deque

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        queue = deque([(p, q)])
        while queue:
            node_p, node_q = queue.popleft()
            if not node_p and not node_q:
                continue
            if not node_p or not node_q:
                return False
            if node_p.val != node_q.val:
                return False
            queue.append((node_p.left, node_q.left))
            queue.append((node_p.right, node_q.right))
        return True

復雜度分析

• 時間復雜度：O(n)，每個節點訪問一次。
• 空間復雜度：O(n)，最壞情況下隊列存儲所有葉子節點。

方法三：迭代法（深度優先搜索）

類似BFS，但使用棧實現深度優先搜索（DFS）。

代碼實現（Python）

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        stack = [(p, q)]
        while stack:
            node_p, node_q = stack.pop()
            if not node_p and not node_q:
                continue
            if not node_p or not node_q:
                return False
            if node_p.val != node_q.val:
                return False
            stack.append((node_p.left, node_q.left))
            stack.append((node_p.right, node_q.right))
        return True

復雜度分析

• 時間復雜度：O(n)。
• 空間復雜度：O(h)，h 為樹的高度。

邊界條件與注意事項

1. 空樹處理：兩棵樹均為空時返回 true。
2. 節點值類型：題目中節點值通常是整數，但實際應用中需考慮其他類型。
3. 樹的結構差異：即使部分子樹相同，整體結構不同仍需返回 false。

擴展思考

變種問題

1. 對稱樹：LeetCode 101題（Symmetric Tree）是相同樹的變種，要求樹鏡像對稱。
2. 子樹匹配：LeetCode 572題（Subtree of Another Tree）判斷一棵樹是否是另一棵樹的子樹。

優化方向

• 并行遍歷：對于大規模樹，可探索并行化遞歸或迭代。
• 短路優化：在迭代中提前終止不必要的比較。

總結

解決“相同的樹”問題主要有遞歸和迭代兩種思路： - 遞歸法：代碼簡潔，適合樹深度不大的場景。 - 迭代法：通過隊列或棧實現，避免遞歸棧溢出風險。

根據實際場景選擇合適的方法，并注意邊界條件處理。

附錄：完整測試用例

# 測試用例1：兩棵樹相同
p = TreeNode(1, TreeNode(2), TreeNode(3))
q = TreeNode(1, TreeNode(2), TreeNode(3))
assert Solution().isSameTree(p, q) == True

# 測試用例2：結構不同
p = TreeNode(1, TreeNode(2))
q = TreeNode(1, None, TreeNode(2))
assert Solution().isSameTree(p, q) == False

”`