/*
 * 演算法 / Algorithm:
 * 一棵樹對稱 ⇔ 左子樹與右子樹互為鏡像。
 * A tree is symmetric iff its left and right subtrees mirror each other.
 * 遞迴比較：兩邊的值相等，且「A左對B右、A右對B左」。
 * Recurse: values equal, and A.left~B.right and A.right~B.left.
 */

// LeetCode 已定義好這個結構，這裡列出方便理解 / LeetCode predefines this struct; shown for clarity:
// struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; };

#include <stdbool.h>  // 讓我們可以用 bool / true / false / gives us bool, true, false

// 輔助函式：判斷 a 和 b 兩棵子樹是否互為鏡像
// Helper: are subtrees a and b mirror images of each other?
static bool isMirror(struct TreeNode* a, struct TreeNode* b) {
    // 情況一：兩個都是空節點 → 它們對稱 / Case 1: both empty → they mirror.
    if (a == NULL && b == NULL) return true;
    // 情況二：只有一個是空 → 結構不對稱 / Case 2: exactly one empty → not symmetric.
    // (a==NULL || b==NULL) 能走到這裡代表「不是兩個都空」，所以只要有一個空就回傳 false
    // Reaching here means "not both null"; if either is null, they can't match.
    if (a == NULL || b == NULL) return false;
    // 情況三：兩個都非空，比較數值；不等就不對稱 / Case 3: both non-null; values must match.
    if (a->val != b->val) return false;
    // 遞迴：外側(a左,b右) 且 內側(a右,b左) 都要是鏡像
    // Recurse: outer pair (a.left,b.right) AND inner pair (a.right,b.left) must both mirror.
    // && 是「而且」：只有兩邊都 true，整體才 true / && means both must hold.
    return isMirror(a->left, b->right) && isMirror(a->right, b->left);
}

bool isSymmetric(struct TreeNode* root) {
    // 空樹視為對稱 / An empty tree is symmetric.
    if (root == NULL) return true;
    // 把「整棵樹是否對稱」轉化為「左子樹與右子樹是否互為鏡像」
    // Reduce "is the whole tree symmetric" to "do left and right subtrees mirror?"
    return isMirror(root->left, root->right);
}