反轉二叉樹演算法詳解：遞迴與迭代兩種 C/C++ 實作

一、問題定義

給定一棵二叉樹，交換每個節點的左右子樹，得到鏡像樹。LeetCode 226 經典題目。

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

二、資料結構定義

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

三、遞迴解法：簡潔優雅

後序遍歷思想：先反轉左右子樹，再交換當前節點指標。

struct TreeNode* invertTree(struct TreeNode* root) {
    if (!root) return NULL;
    
    // 遞迴反轉左右子樹
    struct TreeNode *left  = invertTree(root->left);
    struct TreeNode *right = invertTree(root->right);
    
    // 交換
    root->left = right;
    root->right = left;
    
    return root;
}

• 時間複雜度：O(n)，每個節點訪問一次。
• 空間複雜度：O(h)，遞迴呼叫堆疊深度等於樹高 h (最壞 O(n) 傾斜樹)。

四、迭代解法：顯式堆疊/佇列 (BFS/DFS)

DFS + 堆疊 (前序)

struct TreeNode* invertTreeIterative(struct TreeNode* root) {
    if (!root) return NULL;
    
    struct TreeNode **stack = malloc(1024 * sizeof(struct TreeNode*));
    int top = 0;
    stack[top++] = root;
    
    while (top > 0) {
        struct TreeNode *node = stack[--top];
        
        // 交換左右子節點
        struct TreeNode *tmp = node->left;
        node->left = node->right;
        node->right = tmp;
        
        // 將非空子節點入棧 (先右後左或先左後右均可)
        if (node->right) stack[top++] = node->right;
        if (node->left)  stack[top++] = node->left;
    }
    free(stack);
    return root;
}

BFS + 佇列 (層序)

struct TreeNode* invertTreeBFS(struct TreeNode* root) {
    if (!root) return NULL;
    
    struct TreeNode **queue = malloc(1024 * sizeof(struct TreeNode*));
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    while (front < rear) {
        struct TreeNode *node = queue[front++];
        
        struct TreeNode *tmp = node->left;
        node->left = node->right;
        node->right = tmp;
        
        if (node->left)  queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
    free(queue);
    return root;
}

五、Morris 遍歷：O(1) 空間 (進階)

利用線索二叉樹概念，無需堆疊/佇列。此處略過，有興趣可自行研究。

六、測試驗證主程式

#include 
#include 

struct TreeNode { int val; struct TreeNode *left, *right; };

struct TreeNode* newNode(int v) {
    struct TreeNode *n = malloc(sizeof(struct TreeNode));
    n->val = v; n->left = n->right = NULL;
    return n;
}

void printInorder(struct TreeNode *root) {
    if (!root) return;
    printInorder(root->left);
    printf("%d ", root->val);
    printInorder(root->right);
}

int main() {
    // 建立範例樹
    struct TreeNode *root = newNode(4);
    root->left = newNode(2); root->right = newNode(7);
    root->left->left = newNode(1); root->left->right = newNode(3);
    root->right->left = newNode(6); root->right->right = newNode(9);
    
    printf("原中序: "); printInorder(root); puts("");
    
    root = invertTree(root); // 或迭代版
    
    printf("反中序: "); printInorder(root); puts("");
    // 預期: 9 7 6 4 3 2 1 (原中序 1 2 3 4 6 7 9 完全反轉)
    return 0;
}

七、常見面試延伸問題

1. 非二叉樹 (N-ary Tree) 如何反轉？ 將 children 陣列反序。
2. 只反轉特定層級？ BFS 記錄層級，條件交換。
3. 原地修改 vs 建立新樹？ 題目通常要求原地，空間 O(1) 或 O(h)。
4. 驗證兩棵樹是否互為鏡像？ 同步遍歷比較 left.val == right.val。