前言

今天我們要來挑戰的題目是 Invert Binary Tree（反轉二元樹）。這題目非常直觀：我們需要將二元樹的每個節點的左右子樹交換，從而生成一個反轉的二元樹。其實有點像照鏡子一樣，將每個節點的左右交換。這道題目很適合使用遞迴來解，那就讓我們一起來看具體的做法吧！

英文題目 Invert Binary Tree

難度：Easy

題目描述：
Given the root of a binary tree, invert the tree, and return its root.
給定一棵二元樹的根節點 root，請反轉這棵樹並返回反轉後的根節點。

範例 1：

輸入： root = [4,2,7,1,3,6,9]

輸出： [4,7,2,9,6,3,1]

解釋： 輸入的二元樹：

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

反轉後的二元樹：

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

範例 2：

輸入： root = [2,1,3]

輸出： [2,3,1]

範例 3：

輸入： root = []

輸出： []

中文描述

給定一棵二元樹，將樹的左右子樹反轉，並返回反轉後的根節點。

思路

反轉二元樹其實就是將每個節點的左右子樹互換，這個操作可以通過遞迴來完成。
遞迴的過程中，我們會處理每一個節點，將它的左子樹和右子樹交換，然後對交換後的左右子樹進行同樣的操作。

詳細步驟

1. 基準條件：

   • 如果當前節點為空，直接返回 null，這是遞迴的終止條件。

2. 交換左右子樹：

   • 我們交換當前節點的左右子樹，即 left 和 right 節點互換。

3. 遞迴反轉子樹：

   • 交換完當前節點的左右子樹後，我們需要遞迴處理該節點的左右子樹，確保所有子樹也被反轉。

4. 返回根節點：

   • 最後返回已經反轉過的根節點，這樣整棵樹就被成功反轉。

實作

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val === undefined ? 0 : val);
        this.left = (left === undefined ? null : left);
        this.right = (right === undefined ? null : right);
    }
}

function invertTree(root: TreeNode | null): TreeNode | null {
    // 基準條件：如果節點為空，直接返回 null
    if (root === null) return null;

    // 交換左右子樹
    const temp = root.left;
    root.left = root.right;
    root.right = temp;

    // 遞迴反轉左右子樹
    invertTree(root.left);
    invertTree(root.right);

    // 返回反轉後的根節點
    return root;
}

解題心法

1. 遞迴的應用：

   • 這道題目非常適合使用遞迴。遞迴的思路就是，我們處理當前節點後，將同樣的邏輯應用到其左子樹和右子樹上，這樣就能保證整棵樹都會被處理。

2. 左右子樹的交換：

   • 我們用一個臨時變數 temp 來存儲左子樹，然後將左子樹設為右子樹，右子樹設為原來的左子樹。這樣每個節點的左右子樹都被互換了。

3. 基準條件：

   • 遞迴的基準條件是節點為 null。當我們到達一個空節點時，不需要進行任何處理，直接返回 null 即可。

為什麼這樣處理？

這種遞迴的處理方式直接且有效，每次都只需要處理當前節點的左右子樹交換，然後將問題分解為對左右子樹進行同樣的操作。整個操作會遍歷每個節點，時間複雜度是 O(n)，n 是樹中節點的數量。

本次要點：

• 使用遞迴來處理每個節點的左右子樹交換。
• 交換完後對左右子樹進行同樣的遞迴處理。
• 遞迴的基準條件是節點為空，這是遞迴的終止條件。

這樣看下來，反轉二元樹的操作其實就是一個很直觀的左右交換過程吧！
只要理解了遞迴的應用，這道題目就變得非常簡單。希望你在解這題後，對二元樹的遞迴操作更加熟悉了！
我們下次再來挑戰更多有趣的題目吧！🌟