在這道題目中，我們要判斷兩棵二元樹是否完全相同。兩棵二元樹被認為是相同的當且僅當它們的結構相同，且相同位置的節點具有相同的值。

題目：
給定兩棵二元樹 p 和 q，寫一個函式來檢查它們是否相同。

• 輸入：兩個二元樹的根節點 p 和 q。
• 輸出：如果這兩棵樹相同，回傳 true；否則，回傳 false。

範例：
範例 1：

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

這兩棵樹的結構和每個節點的值都是一樣的，所以它們是相同的。

範例 2：

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

這兩棵樹的結構不同，q 的左子節點為 null，而 p 的左子節點為 2，因此它們不相同。

範例 3：

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

這兩棵樹的結構相同，但對應位置的節點值不同，因此它們不相同。

解題思路

要判斷兩棵二元樹是否相同，可以使用遞迴來遍歷兩棵樹的每個節點，並比較它們的值。

廣度優先搜尋 BFS

基本處理情況步驟如下，

• 如果 p 和 q 都是 nullptr，那麼它們是相同的，回傳 true。
• 如果其中一個是 nullptr 而另一個不是，那麼它們不相同，回傳 false。

然後用兩個 queue 分別進行二元樹遍歷，

• 如果 node1->left 和 node2->left 的節點值不相同，回傳 false。
• 如果 node1->left 和 node2->left 有值才分別推入 queue，若其中一個為空而另一個不為空，則不相同，回傳 false。
• right 也同上比照辦理。

實作：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 若兩棵樹都為空，則相同
        if (p == nullptr && q == nullptr)
            return true;
        // 若其中一棵為空而另一棵不為空，則不相同
        if (p == nullptr || q == nullptr)
            return false;

        queue<TreeNode*> q1;
        queue<TreeNode*> q2;
        q1.push(p);
        q2.push(q);

        while (!q1.empty()) {
            TreeNode* node1 = q1.front();
            q1.pop();

            TreeNode* node2 = q2.front();
            q2.pop();

            // 若節點值不相同，則不相同
            if (node1->val != node2->val)
                return false;

            if (node1->left && node2->left) {
                q1.push(node1->left);
                q2.push(node2->left);
            } else if (node1->left && !node2->left ||
                       !node1->left && node2->left) {
                return false;
            }

            if (node1->right && node2->right) {
                q1.push(node1->right);
                q2.push(node2->right);
            } else if (node1->right && !node2->right ||
                       !node1->right && node2->right) {
                return false;
            }
        }
        return true;
    }
};

遞迴版本

基本處理情況步驟如下，

• 如果 p 和 q 都是 nullptr，那麼它們是相同的，回傳 true。
• 如果其中一個是 nullptr 而另一個不是，那麼它們不相同，回傳 false。
• 如果 p 和 q 的節點值不相同，回傳 false。

如果根節點相同，則繼續遞迴比較它們的左子樹和右子樹，只有當兩者的左子樹和右子樹都相同時，這兩棵樹才被認為是相同的。

實作：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        // 若兩棵樹都為空，則相同
        if (p == nullptr && q == nullptr)
            return true;
        // 若其中一棵為空而另一棵不為空，則不相同
        if (p == nullptr || q == nullptr)
            return false;

        // 若節點值不相同，則不相同
        if (p->val != q->val)
            return false;
        
        // 遞迴檢查左子樹與右子樹
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

參考：
#100. Same Tree