這道題目要求我們反轉一棵二元樹，將它的左子樹和右子樹互換。這個操作類似於將樹沿著垂直軸左右鏡像翻轉。

題目：
給定一棵二元樹的根節點 root，將該二元樹反轉，並回傳其根節點。

• 輸入：一個二元樹的根節點 root。
• 輸出：反轉後的二元樹。

範例：

範例 1：

輸入：
     4
   /   \
  2     7
 / \   / \
1   3 6   9

輸出：
     4
   /   \
  7     2
 / \   / \
9   6 3   1

範例 2：

輸入：
  2
 / \
1   3

輸出：
  2
 / \
3   1

範例 3：

輸入：root = []
輸出：[]

解題思路:遞迴法

要反轉二元樹的話，可以思考看看能否將這個問題猜分成子問題分別去解決，可以的話就有機會使用遞迴法來解決，在這邊可以發現問題可以區分成將左子樹反轉跟將右子樹反轉，那麼就可以嘗試看看用遞迴來解，

然後要處理 root 為 nullptr 的情況，

實作：

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr)
            return root;

        // 交換左右子樹
        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;

        // 遞迴處理子樹
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

上面的還可以寫得更漂亮的空間，改用 std::swap 這樣寫起來比較簡潔也節省寫 code 時間，

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr)
            return root;

        // 交換左右子樹
        swap(root->left, root->right);

        // 遞迴處理子樹
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

解題思路:迭代法

前面用遞迴解，這邊用迭代法來解，加深印象，這邊使用廣度優先 BFS 的方式來解，BFS 前幾次已經練習的上手了，就直接將 BFS 框架套路拿出來直接使用，然後在關鍵的地方作出修改，這邊關鍵的地方是指要 swap 交換的步驟。

/**
 * 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:
    TreeNode* invertTree(TreeNode* root) {
        if (root == nullptr)
            return root;

        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front();
            q.pop();

            swap(node->left, node->right);

            if (node->left != nullptr)
                q.push(node->left);
            if (node->right != nullptr)
                q.push(node->right);
        }
        return root;
    }
};

小技巧：

• 善用 swap 函式節省寫 code 時間

參考：
#226. Invert Binary Tree