101. Symmetric Tree

Easy

Description

給定一棵二元樹的根節點，判斷這棵樹是否是鏡像對稱的（左右子樹互為鏡像）。

Example:

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

Intuition#

鏡像對稱意味著左子樹的左邊等於右子樹的右邊，左子樹的右邊等於右子樹的左邊。

將問題轉化為：比較兩棵子樹是否互為鏡像
兩個節點互為鏡像的條件：值相同，且 A 的左子樹與 B 的右子樹鏡像，A 的右子樹與 B 的左子樹鏡像

Approaches#

⭐ 1: Recursive DFS#

概念: 遞迴比較左右子樹是否鏡像，交叉配對比較
時間複雜度: O(n)，每個節點訪問一次
空間複雜度: O(h)，遞迴堆疊深度

class Solution {
    fun isSymmetric(root: TreeNode?): Boolean {
        return isMirror(root?.left, root?.right)
    }

    private fun isMirror(left: TreeNode?, right: TreeNode?): Boolean {
        if (left == null && right == null) return true
        if (left == null || right == null) return false
        return left.`val` == right.`val` &&
               isMirror(left.left, right.right) &&
               isMirror(left.right, right.left)
    }
}

2: Iterative BFS#

概念: 使用佇列成對地比較鏡像位置的節點
時間複雜度: O(n)
空間複雜度: O(n)

class Solution {
    fun isSymmetric(root: TreeNode?): Boolean {
        if (root == null) return true
        val queue = ArrayDeque<TreeNode?>()
        queue.add(root.left)
        queue.add(root.right)
        while (queue.isNotEmpty()) {
            val left = queue.removeFirst()
            val right = queue.removeFirst()
            if (left == null && right == null) continue
            if (left == null || right == null) return false
            if (left.`val` != right.`val`) return false
            queue.add(left.left)
            queue.add(right.right)
            queue.add(left.right)
            queue.add(right.left)
        }
        return true
    }
}

🔑 Takeaways#

Pattern: 雙指標遍歷樹 — 同時遍歷兩個子樹進行比較
關鍵技巧: 鏡像比較的核心是「交叉配對」：左的左配右的右，左的右配右的左