題目
#

題目簡述
#

判斷兩棵二元樹是否相同。

範例
#

Example 1: @img1.jpg

Input: p = [1,2,3], q = [1,2,3]
Output: true
Explanation: 兩棵樹的結構和節點值完全相同。

Example 2: @img2.jpg

Input: p = [1,2], q = [1,null,2]
Output: false
Explanation: 兩棵樹的結構不同，第一棵樹的第二個節點在左子樹，第二棵樹的第二個節點在右子樹。

Example 3:

Input: p = [1,2,1], q = [1,1,2]
Output: false
Explanation: 兩棵樹的結構相同，但節點值不同。

解題思路
#

這題要求我們判斷兩棵二元樹是否相同。兩棵樹被認為是相同的，當且僅當它們的結構相同且所有對應節點的值都相同。

解法
#

遞迴法（Recursive Approach）

使用深度優先搜尋（DFS）來遍歷兩棵樹
比較對應節點的值和結構
遞迴檢查左子樹和右子樹是否相同

步驟
#

基礎情況（Base Cases）：
- 如果兩個節點都為 null，返回 true
- 如果其中一個節點為 null 而另一個不為 null，返回 false
遞迴情況（Recursive Cases）：
- 如果兩個節點都不為 null 且值相等，遞迴檢查左子樹和右子樹
- 如果節點值不相等，返回 false

遞迴邏輯
#

isSameTree(p, q) = 
  if (p == null && q == null) return true
  if (p == null || q == null) return false
  if (p.val != q.val) return false
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right)

例子說明
#

p = [1,2,3], q = [1,2,3]

步驟	比較節點	p值	q值	結果	下一步操作
根節點比較	p.val vs q.val	1	1	相等	繼續檢查子樹
左子樹比較	p.left.val vs q.left.val	2	2	相等	繼續檢查子樹
右子樹比較	p.right.val vs q.right.val	3	3	相等	繼續檢查子樹
葉節點比較	p.left.left vs q.left.left	null	null	相等	返回true
	p.left.right vs q.left.right	null	null	相等	返回true
	p.right.left vs q.right.left	null	null	相等	返回true
	p.right.right vs q.right.right	null	null	相等	返回true
最終結果	-	-	-	所有節點都相同	返回true

完整程式碼
#

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 基礎情況：如果兩個節點都為null，則兩棵樹相同
        if(p == null && q == null) return true;

        // 如果兩個節點都不為null且值相等，則遞迴檢查子樹
        if(p != null && q != null && p.val == q.val){
            // 遞迴檢查左子樹和右子樹是否都相同
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }

        // 其他情況（一個為null另一個不為null，或值不相等）都返回false
        return false;
    }
}