0226. Invert Binary Tree (Easy)

(當然，Medium的拍手也可以多拍幾下啦XD)

Question

Invert a binary tree.

Example:

Input:

1
2
3
4
5

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

1
2
3
4
5

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

分析/解題

題目要求反轉一個二元樹。

我們今天來看一題經典的題目，
這題經典的原因也許不是在於它有多困難，
而是在於這問題背後的故事XD

或許另一方面也可以看看他本人在Quora上的回應。
所以演算法很重要有沒有XDD
(據稱有一種說法是說當時的題目是要求min-max的反轉，這邊暫不討論，
我們以左右反轉為準)

相信大家經過前面的一堆二元樹相關題目以後，
應該已經對二元樹駕輕就熟了，應該可以輕鬆地寫出遞迴方式的版本。

跟之前的Symmetric Tree相似，
只是這次我們直接將一棵樹的左右節點交換，
除了交換以外，它們的左右子樹的部分也要再度進行交換。

所以我們會拆成：

1. 檢查root是不是null (是的話代表這條路到底了，直接回傳null)
2. 將root.left和root.right進行交換
3. 將root.left和root.right分別做為參數，呼叫函式進行遞迴

Java

Python寫得再簡單一點，不過意思是一樣的XD

Python

你以為這樣就結束了嗎？
我們將繼續來探討一下如果是迭代解的話該怎麼處理。

如果思考一下前面的遞迴解，
會發現一件事情：
對於一個我們造訪的節點而言，
我們所影響到的只有其左節點和右節點，
當下這個節點的値並不會受任何影響。
所以我們只需要保證當走到這個節點的時候，
關於這個節點以上的操作已經做完 即可，
那麼要保證這點的話，只要使用level order 的方式，
我們按順序操作即可做完所有反轉的動作。

由於是先將同一層的做完才會進到下一層，
也可以視作是BFS的方式。
按順序作的話，
可以使用Queue來處理這樣子的問題，步驟大致上是：
0. 檢查root是否為NIL，是的話直接回傳NIL

1. 建立一個queue(python請用deque )
2. 將root放入queue中
3. 每次從queue中取出一個節點，將其左右位置互換 ，
   並分別將左右節點中非NIL的節點放入queue中
4. 重複3直到queue中沒有節點
5. 回傳root

Java:

Python:

面試實際可能會遇到的問題

「時間/空間複雜度？」
(因每個節點均要和另一個位置進行對調，所以時間複雜度為O(N)。
空間複雜度會受到樹的平衡程度影響。
平衡狀態 的話空間複雜度對遞迴解來說是O(logN)(call stack) ，
而對迭代解來說是O(N) (因為最大是最底部那層)
(這時候反而越不平衡每層的節點會越不容易太多))

「這兩種解哪種是DFS？哪種是BFS？」
(遞迴解是DFS(一路走到最深才回頭)，迭代解是BFS(當層走完才往下層走))

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~