一、題目介紹
今天要解的題目是LeetCode的Invert Binary Tree，中文可以稱為「反轉二元樹」。

題目會給定一棵二元樹root，需要將這棵樹進行反轉，也就是將每一個節點的左子樹與右子樹交換。

例如原本的二元樹：

反轉之後會變成：

可以看到

• 4的左右子樹交換
• 2的左右子樹交換
• 7的左右子樹交換
• 每個節點都進行相同的操作

因此這題的核心就是：將每個節點的left與right交換。
如果root為空，則不需要進行任何操作，直接回傳空節點即可。

二、解題思路
這題可以使用遞迴處理。
因為二元樹本身具有遞迴結構，每一個節點底下又可以看成一棵新的二元樹，所以可以從根節點開始處理。

對於目前的節點，可以按照以下步驟
1. 如果節點為空
如果目前節點是null或None，代表已經走到底部，不需要再進行交換。
直接回傳即可。

2. 交換左右子樹
如果節點存在，就先將 left ↔ right 進行交換。

3. 繼續處理左右子樹
交換完成後，再分別對新的左子樹與右子樹進行相同的操作。

三、解題流程
以以下二元樹為例：

首先從根節點4開始。
原本
4.left = 2
4.right = 7

交換之後
4.left = 7
4.right = 2

接著繼續處理7
7.left = 6
7.right = 9

交換
7.left = 9
7.right = 6

再處理2
2.left = 1
2.right = 3

交換
2.left = 3
2.right = 1

最後得到

不是只有根節點4要交換，而是整棵樹的每一個節點都要交換。

四、Java實作

五、Python實作

六、時間與空間複雜度
Java

• 時間複雜度：O(n)
  • 每個節點都需要被訪問一次，並進行左右子樹交換。
  • 假設二元樹共有n個節點，就需要處理n個節點，因此時間複雜度為：O(n)
• 空間複雜度：O(h)
  • 由於使用遞迴，每一次遞迴呼叫都會使用Call Stack。
  • h代表二元樹的高度：
    • 平衡二元樹：約O(log n)
    • 最壞情況，樹退化成單邊鏈狀：O(n)
• 因此最壞情況為：O(n)

Python

• 時間複雜度：O(n)
  • 每個節點都會被訪問一次，因此時間複雜度為O(n)。
• 空間複雜度：O(h)
  • 因為使用遞迴，所以需要使用Call Stack儲存目前的遞迴狀態。
  • 其中h為樹的高度，最壞情況為O(n)。

七、Java與Python解法比較

八、實作結果
Leetcode測試結果：Accepted

九、今日學習心得
今天透過Invert Binary Tree這題，進一步練習了Binary Tree的基本操作。

和昨天的Maximum Depth of Binary Tree相比，兩題都使用到了遞迴，但目的不太一樣。

Day 09是透過DFS走訪左右子樹，取得左右子樹的最大深度；今天則是在走訪每個節點的過程中，直接修改節點的左右子樹關係。

這讓我更加理解二元樹具有遞迴結構的特性。每一個節點都可以視為一棵小型的二元樹，因此只要能處理「目前節點」以及「左右子樹」，就可以透過遞迴完成整棵樹的操作。

另外，今天也注意到Java和Python在變數交換上的語法差異。Java通常需要使用暫存變數，而Python可以透過多重指定直接完成交換。

這題雖然程式碼不長，但讓我更熟悉了TreeNode、左右子樹以及遞迴操作，對之後學習Binary Tree Traversal、DFS和BFS都很有幫助。