226. Invert Binary Tree

──────────────────────────────────────────────────────────────────────

把二元樹左右翻轉（每個節點的左右子樹對調）。

思路

「翻轉整棵樹」聽起來要做很多事，但用遞迴的角度看只有一句話：

每個節點都把自己的左右子樹交換就好。

因為交換是對每個節點獨立的動作，遞迴下去自然就會把整棵樹都翻完。不需要先想「整體變成什麼樣」，只要想「站在一個節點上我該做什麼」—— 這是樹遞迴最重要的思考方式。

base case 是空節點：什麼都不用做，直接回傳。回傳 root（也就是 None）而不是硬回傳 None，是為了讓上一層可以直接把回傳值接上去。

前序還是後序都可以，這題是少數兩者皆可的例子 —— 因為「交換左右指標」和「處理子樹」互不影響。先交換再遞迴（前序）或先遞迴再交換（後序）結果一樣。

解題方向

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
        return root

這一行同時做完了遞迴和交換，關鍵在 Python 的多重賦值會先把右邊整個算完再一次寫入。所以 self.invertTree(root.right) 和 self.invertTree(root.left) 都是對還沒被修改的原始子樹呼叫的，不會互相污染。

如果拆成兩行寫就會出事：

        root.left = self.invertTree(root.right)     # root.left 被蓋掉了
        root.right = self.invertTree(root.left)     # 這裡的 root.left 已經是新的了

第二行拿到的 root.left 已經是剛才寫入的值，等於把同一邊翻了兩次。要拆行就得先存起來：

        left, right = root.left, root.right
        root.left = self.invertTree(right)
        root.right = self.invertTree(left)

「先存後改」跟鏈結串列題是同一個通則 —— 只要一個賦值會蓋掉等下還要用的東西，就先存起來。

補充

這題有名的原因是 Homebrew 作者發過一則推文說 Google 因為他不會在白板上翻轉二元樹而拒絕了他。所以它常被當成「基本功檢查」，重點不在難度，而在能不能乾淨俐落地寫出來並解釋清楚。

迭代版只要把任何一種遍歷的「處理節點」換成交換就好，例如用佇列：

        if not root:
            return None
        queue = deque([root])
        while queue:
            node = queue.popleft()
            node.left, node.right = node.right, node.left
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        return root

因為交換與遍歷順序無關，所以 BFS、前序、後序都行 —— 這也回頭印證了上面說的「這題前後序皆可」。

相關題：100. Same Tree（同步比較兩棵樹；把一棵翻轉後再比就是判斷對稱）、114. Flatten Binary Tree to Linked List（同樣是原地改指標，但順序有講究）。整理見 Tree 遍歷模板。

複雜度

時間 $O (n)$ — 每個節點交換一次
空間 $O (h)$ — 遞迴堆疊，h 是樹高（BFS 版則是 $O (w)$ ，w 是最寬一層的節點數）

其中 n 是節點數。平衡樹的 h 是 $O (\log n)$ 、退化成鏈時是 $O (n)$ 。