LeetCode 100：Same Tree（判斷兩棵二叉樹是否相同）

一、題目描述

給定兩棵二叉樹的根節點 p 和 q，編寫函數檢查它們是否相同。

兩棵樹相同的定義：結構完全一致，且對應節點的值相等。

二、解題思路：遞歸

採用深度優先搜索（DFS）遞歸比較：

1. 若兩節點均為空，返回 true。
2. 若一個為空、一個不為空，返回 false。
3. 若兩節點值不等，返回 false。
4. 遞歸比較左子樹和右子樹，均相同則返回 true。

三、代碼實現（C++）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        if (p->val != q->val) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

四、複雜度分析

• 時間複雜度：O(min(N, M))，N、M 為兩樹節點數
• 空間複雜度：O(H)，H 為樹高（遞歸棧）

此為標準遞歸解法，代碼簡潔易懂。