題目說明
Day 16 - 226. Invert Binary Tree
給定一個二元樹，將其左右子樹鏡像翻轉。

範例：
Input:

4

/
2 7
/ \ /
1 3 6 9

Output:

4

/
7 2
/ \ /
9 6 3 1

程式碼

Python 解法
解法 1：遞迴 DFS

class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root: TreeNode) -> TreeNode:
if not root:
return None

交換左右子樹

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

解法 2：BFS（Queue）

from collections import deque

def invertTree(root: TreeNode) -> TreeNode:
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

Java 解法
解法 1：遞迴 DFS

public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}

解法 2：BFS（Queue）

import java.util.*;

public class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) return null;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode temp = node.left;
        node.left = node.right;
        node.right = temp;

        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    return root;
}

}

複雜度分析

• 時間複雜度：O(n)，每個節點都會被訪問並交換一次。

• 空間複雜度：

  • 遞迴 DFS：O(h)，h 為樹的高度（最壞 O(n)，最佳 O(log n)）。
  • BFS：O(w)，w 為樹的最大寬度（最壞可能接近 O(n)）。