226. Invert Binary Tree

題目 / Problem

中文： 給定一棵二元樹的根節點 root，把整棵樹「左右翻轉」（把每個節點的左子樹和右子樹互相交換），然後回傳翻轉後的根節點。

English: Given the root of a binary tree, invert it — for every node, swap its left child and right child — then return the root of the inverted tree.

約束 / Constraints: - 節點數量在 [0, 100] 範圍內 / The number of nodes is in the range [0, 100] (so the tree may be empty). - -100 <= Node.val <= 100（節點值的範圍 / value range of each node）。

範例 / Worked Example:

Input:  root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

原本 4 的左邊是以 2 為根的子樹、右邊是以 7 為根的子樹；翻轉後 4 的左邊變成 7、右邊變成 2，而且每個子樹內部也同樣被翻轉。 Originally node 4 has the subtree rooted at 2 on the left and 7 on the right; after inverting, 7 is on the left and 2 on the right, and every subtree inside is mirrored the same way.

名詞解釋 / Glossary

• 二元樹 / Binary tree： 一種樹狀資料結構，每個節點最多有兩個孩子，分別叫「左子節點」和「右子節點」。A tree structure where each node has at most two children, called the left child and the right child.
• 節點 / Node： 樹裡的一個元素。在本題每個節點是一個結構，內含一個整數值 val、指向左孩子的指標 left、指向右孩子的指標 right。An element of the tree holding a value val and two pointers left and right.
• 根節點 / Root： 樹最頂端、沒有父節點的那個節點；從它可以走到所有其他節點。The topmost node with no parent; every other node is reachable from it.
• 葉節點 / Leaf： 沒有任何孩子（left 和 right 都是空）的節點。A node whose left and right are both null/empty.
• 空指標 / NULL (C) · nullptr (C++)： 一個「不指向任何東西」的特殊指標值，用來表示「這裡沒有節點」。A special pointer value meaning "points to nothing"; we use it to mark a missing child or an empty tree.
• 指標 / Pointer： 一個變數，裡面存的是「另一個東西在記憶體中的位址」。node->left 就是順著位址找到左孩子。A variable that stores the memory address of something else; node->left follows that address to reach the left child.
• 遞迴 / Recursion： 一個函式呼叫它自己來解決更小的同類問題。A function that calls itself to solve a smaller version of the same problem.
• DFS（深度優先搜尋）/ Depth-First Search： 一種走訪樹的方式：先儘量往深處走，處理完一整條路徑再回頭。這裡用遞迴自然實現 DFS。A traversal strategy that goes as deep as possible before backtracking; recursion implements it naturally here.
• 佇列 / Queue： 一種「先進先出（FIFO）」的容器，用來實作 BFS（廣度優先）走訪。A first-in-first-out container, used to do a breadth-first traversal iteratively. (Mentioned as an alternative; our main solution uses recursion.)

思路

我們要把每個節點的左右子樹交換。最直接的想法是：從根節點開始，把它的 left 和 right 兩個指標對調就好。但只換根節點是不夠的，因為題目要求整棵樹每一層、每個節點都要翻轉。關鍵觀察是：翻轉一整棵樹，等於「先交換根節點的左右孩子指標，然後再分別翻轉左子樹和右子樹」。因為左右子樹本身也是二元樹，這就變成同一個問題的縮小版，天生適合用遞迴解。遞迴的終止條件（base case）是遇到空節點（NULL）——空樹翻轉還是空樹，直接回傳即可，這也順便處理了空輸入 [] 的情況。每個節點只被拜訪一次，交換指標是 O(1) 的操作，所以整體很有效率。注意交換時要用一個暫存變數，否則會把其中一個指標覆蓋掉。這裡我們對每個節點「先交換、再往下遞迴」，其實先交換或後交換都可以，因為交換動作和「哪個子樹先被處理」互不影響。

We need to swap the left and right child of every node. The simplest idea is to swap left and right at the root — but that alone only mirrors the top level; the problem wants the whole tree mirrored. The key insight is that inverting a tree equals "swap the root's two child pointers, then invert each of its subtrees." Since each subtree is itself a binary tree, this is a smaller instance of the exact same problem, which makes recursion (a DFS) the natural fit. The base case is hitting an empty node (NULL): an empty tree inverted is still empty, so we just return it — and this also transparently handles the empty-input [] case. Every node is visited once and swapping pointers is an O(1) step, so the algorithm is efficient. One implementation detail: use a temporary variable when swapping, or you'll clobber one of the pointers. Whether you swap before or after recursing into the children doesn't matter, because the swap and the order of recursion are independent.

逐步走查 / Walkthrough

輸入 / Input: [4,2,7,1,3,6,9]，對應的樹 / which is the tree:

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

我們用 invert(node) 表示「翻轉以 node 為根的子樹」。呼叫順序（DFS，先交換再往左、往右）：

We call invert(node) = "invert the subtree rooted at node". Call order (DFS, swap first then go left, then right):

最終樹 / Final tree:

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

層序輸出 / Level-order output: [4,7,2,9,6,3,1] ✅

Solution — C

/*
 * 演算法 / 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;
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 遞迴 DFS：交換每個節點的 left/right，再翻轉兩棵子樹。
 * Recursive DFS: swap each node's left/right, then invert both subtrees.
 * 空節點是遞迴終止條件 / a null node is the base case.
 */

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

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 空節點（nullptr）無需翻轉，直接回傳 / a null node needs no work — return it.
        // nullptr 是 C++ 的空指標字面值，比 C 的 NULL 更型別安全。
        // nullptr is C++'s typed null-pointer literal, safer than C's NULL.
        if (root == nullptr) {
            return nullptr;
        }

        // std::swap 是 STL 提供的工具，一行就能交換兩個變數的值，內部會用暫存變數。
        // std::swap is an STL helper that exchanges two values in one line (it uses a temp internally),
        // 這樣就不用自己手寫 temp，交換 root 的左右兩個指標。
        // so we avoid a manual temp; here we swap root's left and right pointers.
        std::swap(root->left, root->right);

        // 遞迴翻轉左子樹 / recursively invert the left subtree.
        invertTree(root->left);

        // 遞迴翻轉右子樹 / recursively invert the right subtree.
        invertTree(root->right);

        // 回傳翻轉後的根 / return the inverted root.
        return root;
    }
};

複雜度 / Complexity

• Time: O(n) — 其中 n 是節點總數。每個節點恰好被拜訪一次，且在每個節點上做的交換是 O(1) 常數時間，所以總時間與節點數成正比。Where n is the number of nodes; each node is visited exactly once and does O(1) work (a pointer swap), so total time is linear in the node count.
• Space: O(h) — 其中 h 是樹的高度，來自遞迴呼叫堆疊（call stack）的深度。最壞情況樹退化成一條鏈時 h = n，變成 O(n)；平衡樹則約為 O(log n)。Where h is the tree height, from the recursion call stack. In the worst case (a degenerate/linked-list-like tree) h = n → O(n); for a balanced tree it's about O(log n).

Pitfalls & Edge Cases

• 空樹 / Empty tree ([])： 一定要先檢查 root == NULL 再存取 root->left，否則會對空指標解參考造成崩潰。我們把它當作遞迴 base case，自然安全處理。You must check for null before dereferencing root->left, or you'll crash on a null-pointer dereference; our base case handles this cleanly.
• 交換時忘了暫存 / Swapping without a temp： 若直接 root->left = root->right; root->right = root->left;，第二行會把已被覆蓋的值又寫回去，兩個指標最後都指向同一棵子樹。C 版用 temp、C++ 版用 std::swap 都避免了這個陷阱。Doing the two assignments without a temp overwrites one pointer before it's used, leaving both pointing at the same subtree.
• 忘了回傳 root / Forgetting to return root： 題目要求回傳翻轉後的根節點；漏掉 return root; 會回傳錯誤或未定義的值。The problem asks you to return the (same) root; omitting the return breaks the answer.
• 只換根節點 / Only swapping at the root： 只翻最上層而不遞迴進子樹，會漏掉深層的翻轉；遞迴確保每一層都被處理。Mirroring just the top level misses deeper nodes — recursion guarantees every level is inverted.
• 值域不需擔心溢位 / No overflow concern： 值介於 -100..100，我們也只移動指標、不做算術，因此沒有整數溢位問題。Values fit easily and we only move pointers, so there's no arithmetic overflow risk here.