題目
#

leetcode 226 - Invert Binary Tree (題目說明請點連結)

題目簡述
#

反轉一個二元樹。

範例
#

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
Explanation: 反轉前的樹結構如下：

graph TD; A[4] B[2] C[7] D[1] E[3] F[6] G[9] A --> B A --> C B --> D B --> E C --> F C --> G

反轉後的樹結構如下：

graph TD; A[4] B[7] C[2] D[9] E[6] F[3] G[1] A --> B A --> C B --> D B --> E C --> F C --> G

解題思路
#

這題要求我們反轉一個二元樹，即將每個節點的左右子樹互換。我們可以使用遞迴的方法來實現這個操作。

解法
#

遞迴反轉法（Recursive Approach）

如果當前節點為空，返回 null
交換當前節點的左右子樹
遞迴反轉左子樹
遞迴反轉右子樹
返回當前節點

步驟
#

初始化：
- 檢查根節點是否為空
遞迴反轉：
- 交換左右子樹
- 遞迴反轉左子樹
- 遞迴反轉右子樹
返回結果：
- 返回反轉後的根節點

例子說明
#

反轉前的樹結構：

graph TD; A[4] B[2] C[7] D[1] E[3] F[6] G[9] A --> B A --> C B --> D B --> E C --> F C --> G

反轉後的樹結構：

graph TD; A[4] B[7] C[2] D[9] E[6] F[3] G[1] A --> B A --> C B --> D B --> E C --> F C --> G

完整程式碼
#

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        if( root == null) return null;

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

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

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