LeetCode 226：Invert Binary Tree（翻轉二叉樹）

一、題目描述

翻轉一棵二叉樹：將每個節點的左、右子樹交換。

示例：

     4           4
   /   \       /   \
  2     7  →  7     2
 / \   / \   / \   / \
1   3 6   9 9   6 3   1

二、解題思路：後序遍歷遞歸

採用後序遍歷（左-右-根），先遞歸翻轉左右子樹，再交換當前節點的左右指針。這樣保證底層先完成翻轉，再向上傳遞。

三、代碼實現（C++）

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (!root) return nullptr;
        // 遞歸翻轉左右子樹
        TreeNode* newLeft = invertTree(root->right);
        TreeNode* newRight = invertTree(root->left);
        // 交換
        root->left = newLeft;
        root->right = newRight;
        return root;
    }
};

四、迭代法（BFS）

也可使用層序遍歷（隊列）迭代交換：

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        TreeNode* node = q.front(); q.pop();
        swap(node->left, node->right);
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
    return root;
}

五、複雜度分析

• 時間複雜度：O(N)，訪問每個節點一次
• 空間複雜度：O(H) 遞歸棧 或 O(N) 隊列

本題源自 Max Howell 的著名推特：「Google: 90% of our engineers use the software you wrote (Homebrew), but you can't invert a binary tree on a whiteboard so fuck off.」