LeetCode 226 翻轉二叉樹：遞歸與迭代（BFS/DFS）雙重解法完整對比

問題描述

給定二叉樹根節點，交換每個節點的左右子樹，返回翻轉後的根節點。原地修改即可。

遞歸解法（最簡潔）

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

後序遍歷思想：先翻轉子樹，再交換左右指針。時間 O(n)，空間 O(h)（遞歸棧）。

迭代解法一：BFS（層序遍歷）

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

空間 O(w)（最大層寬），最壞 O(n)。

迭代解法二：DFS（顯式棧）

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    stack st; st.push(root);
    while (!st.empty()) {
        TreeNode* cur = st.top(); st.pop();
        swap(cur->left, cur->right);
        if (cur->left) st.push(cur->left);
        if (cur->right) st.push(cur->right);
    }
    return root;
}

前序遍歷順序，空間 O(h)。

Morris 遍歷（O(1) 空間，進階）

利用線索二叉樹思想，無棧無遞歸。代碼較長，適合極端空間受限場景。

性能對比與選擇建議

LeetCode 實測：遞歸 4ms，BFS/DFS 0ms（常數因子差異）。