/*
 * 演算法 / Algorithm:
 * 對每個節點交換其 left 與 right 指標，然後遞迴翻轉左右子樹（DFS）。
 * Swap each node's left/right pointers, then recursively invert both subtrees.
 * base case：空節點直接回傳，順帶處理空樹。
 * Base case: an empty node returns as-is, which also handles an empty tree.
 */

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

struct TreeNode* invertTree(struct TreeNode* root) {
    // 若目前節點是空的（NULL），沒有東西可翻轉，直接回傳 NULL
    // If the current node is empty (NULL), there is nothing to invert — return it.
    if (root == NULL) {
        return NULL;
    }

    // 用暫存變數存住左孩子，避免等一下覆蓋後就找不到它了
    // Save the left child in a temp var so we don't lose it when we overwrite root->left.
    struct TreeNode* temp = root->left;

    // 把左指標指向原本的右孩子 / point the left pointer at the original right child.
    root->left = root->right;

    // 把右指標指向剛剛暫存的原左孩子，交換完成 / point right at the saved original left child.
    root->right = temp;

    // 遞迴翻轉「新的」左子樹（原本的右子樹）/ recursively invert the (now) left subtree.
    invertTree(root->left);

    // 遞迴翻轉「新的」右子樹（原本的左子樹）/ recursively invert the (now) right subtree.
    invertTree(root->right);

    // 回傳這棵已翻轉子樹的根 / return the root of this inverted subtree.
    return root;
}