> ## Content Index
> Fetch the complete content index at: https://blog.anthea.day/llms.txt
> Use this file to discover other available public pages before exploring further.

# LeetCode 100. Same Tree
- URL: https://blog.anthea.day/leetcode-c-e5-88-b7-e9-a1-8c-e7-ad-86-e8-a8-98-12/
- Published: 2023-01-11T15:28:48.000Z
- Updated: 2026-11-07T18:26:18.000Z
- Author: Anthea / 芫荽
- Tags: #Migrated-1792241843742, #Import 2026-10-17 12:57, Coding, LeetCode 刷題筆記

> Given the roots of two binary trees `p` and `q`, write a function to check if they are the same or not.

> Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

**Example 1:**

![](https://blog.anthea.day/content/images/2026/10/0-_y3adj3mrjwkqk1v.jpg)

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

**Example 2:**

![](https://blog.anthea.day/content/images/2026/10/0-mwko0ipcalu2jla3.jpg)

```vbnet
Input: p = [1,2], q = [1,null,2] 
Output: false
```

**Example 3:**

![](https://blog.anthea.day/content/images/2026/10/0-w8preslaetzumucr.jpg)

```vbnet
Input: p = [1,2,1], q = [1,1,2] 
Output: false
```

**Constraints:**

- The number of nodes in both trees is in the range `[0, 100]`.
- `-10^4 <= Node.val <= 10^4`

### 效能

- Time complexity: `O(n)`
- Space complexity: `O(n)`
- Runtime: 101 ms
- Memory: 40 MB

---

### 遞迴比較

關於二元樹的 class 如下：

```kotlin
public class TreeNode { 
    public int val; 
    public TreeNode left; 
    public TreeNode right; 
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { 
        this.val = val; 
        this.left = left; 
        this.right = right; 
    } 
}
```

首先來看最一開始拿到的兩個 TreeNode。如果他們兩個剛好都是 `null`，就代表我們剛好檢視完所有的值了，所以這兩棵樹是一樣的，回傳 `true`。如果一邊是 `null` 但另外一邊不是，就代表兩棵樹的高度不太一樣，所以會回傳 `false`。

```lua
0    0    ---> 相等的樹 
   0    n    ---> 不相等的樹
```

確定好兩邊的 TreeNode 都不是 `null` 後，再比較兩邊的值，如果不一樣就回傳 `false`。

```lua
0    1   ---> 不相等的樹
```

寫成程式碼會長這樣：

```kotlin
public bool IsSameTree(TreeNode p, TreeNode q) { 
    if (p == null && q == null) return true; 
 
    if (p == null || q == null) return false; 
 
    if (p.val != q.val) return false; 
}
```

如果樹不只一層，比如說：

```css
p    q 
   0    0 
  1 2  2 3
```

接下來就是要分別去比左邊 `p = 1, q = 2` 和右邊 `p = 2, q = 3` 的部分。要比的內容其實一樣，先看兩邊有沒有包含 null，都沒有的話就比值，值一樣就繼續往下比左邊和右邊。完整程式碼如下：

```kotlin
public bool IsSameTree(TreeNode p, TreeNode q) { 
    if (p == null && q == null) return true; 
    if (p == null || q == null) return false; 
    if (p.val != q.val) return false; 
 
    var isSameTreeInLeft = IsSameTree(p.left, q.left); 
    var isSameTreeInRight = IsSameTree(p.right, q.right); 
     
    return isSameTreeInLeft && isSameTreeInRight; 
}
```

---

#### 參考資料

- [100\. Same Tree](https://leetcode.com/problems/same-tree/description/?ref=blog.anthea.day)