這題的題目在這裡: 226. Invert Binary Tree
題目敘述
題目會給我們一顆二元樹的根節點，要求我們對齊根節點正中央的虛擬分割線，反轉整顆二元樹。
測試範例
Example 1:
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Example 2:
Input: root = [2,1,3]
Output: [2,3,1]
Example 3:
Input: root = []
Output: []
約束條件
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
演算法
利用DFS遞迴探索整顆樹的性質，來進行鏡像反轉。
- 先交換左子樹和右子樹(在程式碼中，就是交換root.left 和 root.right)
- 遞迴處理下一層(這邊我們使用DFS 比較簡潔)
- 返回樹根root，樹根本身保持不動。
程式碼
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root:
# General case:
# invert child node of current root
root.left, root.right = root.right, root.left
# invert subtree with DFS
self.invertTree( root.left )
self.invertTree( root.right )
return root
else:
# Base case:
# empty tree
return None
複雜度分析
時間複雜度:O( n )
O( n ) 每個節點最多拜訪一次。
空間複雜度:O( n )
O( n ) 空間成本耗費在遞迴呼叫時所建立的call stack，
最深的那一層在最後一層，當樹向左歪斜或向右歪斜時，
最深的深度可以到O( n )
Reference
[1] Python/JS/Java/Go/C++ O(n) by DFS [w/ Visualization] — Invert Binary Tree — LeetCode
