前言

今天我們要來解一個二元樹的題目，叫做 Symmetric Tree。

這題其實還滿有趣的，因為它要我們檢查一棵樹是不是「對稱的」，也就是說這棵樹的左邊和右邊要像鏡子一樣互相反映。不過，這題看起來簡單，實際上要考慮的細節還不少喔！那我們就來看看怎麼解決這個問題吧，準備好鏡子一起來檢查這棵樹是不是對稱的嗎？✨

題目 Symmetric Tree

難度：Easy

題目描述：

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

給定一棵二叉樹的根節點 root，檢查它是否是鏡像對稱的（即，樹的左右兩邊是否互相對稱）。

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

思路

這道題的核心是檢查二叉樹的左右兩邊是否對稱。我們可以將問題轉化為比較兩棵樹是否是鏡像對稱的問題。具體來說，我們可以從以下幾個步驟來解決：

1. 遞迴比較：

   • 這個問題可以通過遞迴來解決，我們比較二叉樹的左子樹和右子樹，並且遞迴檢查每一層節點是否對稱。
   • 如果左子樹的左節點等於右子樹的右節點，且左子樹的右節點等於右子樹的左節點，則繼續比較更下一層的節點。

2. 遞迴的停止條件：

   • 如果同時到達了兩個葉子節點（即兩個節點都為 null），說明這一部分是對稱的。
   • 如果只有一個節點為 null，那麼這棵樹就不是對稱的。

3. 初始情況：

   • 我們從根節點開始，檢查它的左右子樹是否鏡像對稱。

實作

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 isSymmetric(root: TreeNode | null): boolean {
    if (!root) return true;

    function isMirror(left: TreeNode | null, right: TreeNode | null): boolean {
        if (!left && !right) return true; // 都是 null，對稱
        if (!left || !right) return false; // 其中一個是 null，不對稱
        return (left.val === right.val) // 值相同
            && isMirror(left.left, right.right) // 左子樹的左節點 vs 右子樹的右節點
            && isMirror(left.right, right.left); // 左子樹的右節點 vs 右子樹的左節點
    }

    return isMirror(root.left, root.right); // 檢查根節點的左右子樹
}

解題心法

1. 遞迴檢查左右子樹：

   • 我們要檢查每一層的左右子樹是否對稱，因此使用遞迴是一個很自然的解法。遞迴的過程中不斷比較左右子樹的對應節點，保證鏡像對稱。

2. 遞迴終止條件：

   • 當兩個節點都為 null，表示這一層是對稱的；
   • 當只有一個節點為 null，則表示這一層不對稱，遞迴可以提前結束。

3. 考慮極端情況：

   • 當二叉樹是空的時候，根節點為 null，這樣的樹是對稱的，所以我們直接返回 true。

總結

這道 Symmetric Tree 題目通過遞迴檢查左右子樹是否鏡像對稱，解法簡潔明了且具備普遍性。
當你面對需要檢查結構對稱性的問題時，這種遞迴方法會非常有效！
很開心完賽囉！🌳💫