給定一棵二元樹的根節點，將整棵樹左右翻轉（鏡像），回傳翻轉後的根節點。每個節點的左右子樹互換。
Example:
Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1]
Intuition
TIP
對每個節點，交換其左右子節點，然後遞迴處理子樹。
- 翻轉一棵樹 = 交換根的左右子樹 + 分別翻轉左右子樹
- 這是一個天然的遞迴結構，也可以用迭代（BFS/DFS）完成
Approaches
⭐ 1. Recursive DFS — O(n) / O(h)
- Idea: 後序遍歷，先遞迴翻轉左右子樹，再交換左右子節點
- Time:
O(n)，每個節點訪問一次 - Space:
O(h)，遞迴堆疊深度，h 為樹高
class Solution {
fun invertTree(root: TreeNode?): TreeNode? {
if (root == null) return null
val left = invertTree(root.left)
val right = invertTree(root.right)
root.left = right
root.right = left
return root
}
}2. Iterative BFS — O(n) / O(n)
- Idea: 使用佇列進行層序遍歷，對每個節點交換左右子節點
- Time:
O(n) - Space:
O(n)，佇列最多存放一層的節點
class Solution {
fun invertTree(root: TreeNode?): TreeNode? {
if (root == null) return null
val queue: ArrayDeque<TreeNode> = ArrayDeque()
queue.add(root)
while (queue.isNotEmpty()) {
val node = queue.removeFirst()
val temp = node.left
node.left = node.right
node.right = temp
node.left?.let { queue.add(it) }
node.right?.let { queue.add(it) }
}
return root
}
}🔑 Takeaways
- Pattern: 樹的遞迴結構 — 問題可分解為「對當前節點操作 + 遞迴處理子樹」
- Key trick: 遞迴是處理樹結構最直覺的方式，幾乎所有樹的變換問題都能用這個模式