Easy 226. Invert Binary Tree

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

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

Input:
     2
   /   \
  1     3

Output:
     2
   /   \
  3     1

解題思路

這題可以用遞迴的方式來解決，步驟如下：

1. 基本概念
   // 原始樹
        4
      /   \
     2     7
   
   // 翻轉後
        4
      /   \
     7     2
   

2. 遞迴過程
   // 1. 先儲存左子樹
   temp = root.left; // (2)
   
   // 2. 左邊換成右子樹
   root.left = root.right; // (7)
   
   // 3. 右邊換成原本的左子樹
   root.right = temp; // (2)
   
   // 4. 對子節點重複此過程
   

複雜度分析

• 時間複雜度：O(n)，需要遍歷每個節點一次
• 空間複雜度：O(h)，h 是樹的高度，遞迴調用棧的空間

程式碼

function invertTree(root) {
  // 處理邊界情況：空節點直接返回
  if (!root)
    return null;

  // 使用解構賦值交換左右子樹
  [root.left, root.right] = [
    invertTree(root.right), // 遞迴處理右子樹
    invertTree(root.left) // 遞迴處理左子樹
  ];

  return root;
}

程式碼說明

1. 邊界處理
   • 簡潔的條件判斷 if (!root)
2. 現代 JavaScript 特性
   • 使用解構賦值一次完成交換
   • 這樣就可以避免使用變數去維護左右子樹
3. 遞迴處理
   • 同時處理左右子樹
   • 返回處理完的節點

解題心得

1. 遞迴思維
   • 把大問題分解成相同的小問題
   • 找到適當的終止條件很重要
2. 程式碼優化
   • 解構賦值讓交換操作更好懂