// 演算法：遞迴地同時比較兩棵樹。相同 = 根相同 + 左子樹相同 + 右子樹相同。
// Algorithm: recursively compare both trees at once. Same = roots equal
// + left subtrees same + right subtrees same. Visit each node once (DFS).

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    // 邊界1：兩個都是空節點，這條路走到底且一致 / Base 1: both NULL — matched all the way down
    if (p == NULL && q == NULL) return true;

    // 邊界2：只有一個是空，結構對不上 / Base 2: exactly one is NULL — shapes differ
    // （若上面沒回傳，代表不會兩個都為 NULL；這裡任一為 NULL 就是「只有一個」）
    // (if we got past base 1, at most one is NULL; either being NULL means mismatch)
    if (p == NULL || q == NULL) return false;

    // 邊界3：兩個都非空，但值不同 / Base 3: both exist but values differ
    // p->val 是「解參考指標 p 取得節點的 val 欄位」/ p->val dereferences p and reads its val field
    if (p->val != q->val) return false;

    // 當前節點一致，遞迴檢查左子樹與右子樹，兩者都要成立 (&& 短路)
    // Current node matches; recurse on left and right — both must hold (&& short-circuits)
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}