226.Invert Binary Tree

DFS（深度優先搜尋）

想法：
遞迴順序是 先遞迴左右子樹 (post-order)，再交換當前節點左右子節點
在每個節點做交換時，所用的 left 與 right 已經是「各自子樹被反轉過」的結果（這就是為什麼用後序正確）

程式碼：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }

        // 先翻轉左右子樹
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);

        // 再交換
        root.left = right;
        root.right = left;

        return root;
    }
}

—
兩者比較

• 正確性
  • 兩者結果相同，都會把樹完整翻轉成鏡像。
• 時間複雜度
  • DFS（遞迴）：O(n)（每個節點訪問一次）
  • BFS（迭代）：O(n)（每個節點訪問一次）
• 空間複雜度
  • DFS（遞迴）：呼叫堆疊深度為樹高 O(h)。最壞情況（鏈狀）為 O(n)。
  • BFS（迭代）：隊列最大長度在最寬層約 O(width)，對於完全二叉樹約 O(n/2) → O(n)。
• 實作與可讀性
  • DFS：程式最簡潔、直觀（尤其短小樹或面試時容易寫）。
  • BFS：程式稍長但邏輯直觀（層序交換），不會有遞迴深度問題。
• 邊界/穩定性
  • DFS 可能會在極深的樹上發生 stack overflow（遞迴深度太高）。
  • BFS 使用顯式隊列，不會爆呼叫堆疊，但需要更多額外記憶體在寬樹時。
• 選擇建議
  • 若樹高度可控（或語言/環境遞迴安全），用 DFS（遞迴）：寫得快且易懂。
  • 若樹可能非常深（例如退化成鏈）或不想使用遞迴，選 BFS（迭代）（或用顯式 stack 做 DFS 迭代版）。