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

// LeetCode 已定義 TreeNode / LeetCode predefines TreeNode:
// struct TreeNode { int val; TreeNode *left; TreeNode *right; };

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        // 空樹視為對稱 / An empty tree is symmetric.
        if (root == nullptr) return true;
        // 轉化為兩棵子樹是否互為鏡像 / Reduce to: do the two subtrees mirror?
        return isMirror(root->left, root->right);
    }

private:
    // 輔助函式：a 與 b 是否互為鏡像 / Helper: do a and b mirror each other?
    bool isMirror(TreeNode* a, TreeNode* b) {
        // 兩個都空 → 對稱 / Both empty → mirror.
        if (a == nullptr && b == nullptr) return true;
        // 只有一個空 → 不對稱 / Exactly one empty → not a mirror.
        if (a == nullptr || b == nullptr) return false;
        // 值不同 → 不對稱 / Different values → not a mirror.
        if (a->val != b->val) return false;
        // 外側配外側、內側配內側，兩者皆須成立
        // Outer with outer, inner with inner; both must hold.
        return isMirror(a->left, b->right) && isMirror(a->right, b->left);
    }
};