題目描述:反轉一棵二元樹(鏡像翻轉),回傳翻轉後的根節點。
解題思路:遞迴:交換當前節點的左右子節點,然後遞迴反轉左子樹和右子樹。由於先交換後遞迴或先遞迴後交換都可以,最常見的是交換後遞迴。BFS 迭代法也很直觀:逐層交換每個節點的左右孩子。
時間複雜度:O(n) — 每個節點訪問一次。
空間複雜度:O(h) — 遞迴棧(h 為樹高)。
1. If root is null: return null 2. Swap root.left and root.right 3. Invert root.left 4. Invert root.right 5. Return root
迭代層序遍歷 O(n) 時間,O(w) 空間:BFS 逐層交換兒子 — 邏輯相同,空間複雜度更差。
後序遍歷 O(n) 時間,O(h) 空間:遞迴後序,回程時交換 — 邏輯相同。