LeetCode 226. Invert Binary Tree：遞歸與迭代翻轉二叉樹

問題描述

翻轉二叉樹：左右子樹互換。例如：

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

源自 Max Howell 推特：Google 90% 工程師用其 Homebrew，卻不會白板翻轉二叉樹。

遞歸解法

// C++
TreeNode* invertTree(TreeNode* root) {
    if (!root) return root;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

// Python
def invertTree(self, root):
    if not root: return None
    root.left, root.right = root.right, root.left
    self.invertTree(root.left)
    self.invertTree(root.right)
    return root

迭代解法（BFS/DFS）

// BFS 隊列
TreeNode* invertTree(TreeNode* root) {
    if (!root) return root;
    queue q; q.push(root);
    while (!q.empty()) {
        auto 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(w)（隊列寬度），最壞 O(n)

核心考點

基礎數據結構操作、遞歸思維、指針/引用交換、邊界條件（空樹）。面試高頻必會題。