101. Symmetric Tree

Symmetric Tree

題目描述：給定一棵二元樹的根節點 root，判斷此樹是否以根節點為中心左右對稱（即是否為自身的鏡像）。

解題思路：核心觀察是：若一棵樹以中心對稱，則其左子樹與右子樹互為鏡像。我們定義一個輔助函式 isMirror(left, right) 來遞迴判斷兩個子樹是否互為鏡像。

判斷兩個節點 left 和 right 互為鏡像的條件：

1. 兩者皆為 null → 對稱（true）
2. 其中一個為 null 而另一個不是 → 不對稱（false）
3. 兩者的值不相等 → 不對稱（false）
4. 兩者的值相等，且 isMirror(left.left, right.right) 為真，且 isMirror(left.right, right.left) 為真 → 對稱（true）

注意「外側」對應外側、「內側」對應內側：left.left 應與 right.right 鏡像，left.right 應與 right.left 鏡像。

時間複雜度：O(n) — 每個節點恰好被訪問一次，其中 n 為樹中節點的總數。

空間複雜度：O(h) — 遞迴呼叫堆疊的深度等於樹的高度 h。最壞情況（完全退化為鏈狀樹）為 O(n)，最佳情況（完全平衡樹）為 O(log n)。

方法一：迭代 BFS（使用佇列）

• 使用一個佇列，每次同時取出兩個節點進行比較。初始時將 root.left 和 root.right 加入佇列。每輪取出一對節點：若都為 null 則繼續；若一個 null 則回傳 false；若值不同則回傳 false；否則按照鏡像順序將 4 個子節點加入佇列（l.left 配 r.right，l.right 配 r.left）。
• 時間複雜度：O(n)，空間複雜度：O(n)（佇列最多儲存一層節點）

方法二：迭代 DFS（使用堆疊）

• 與 BFS 邏輯相同，但使用 stack 取代 queue，以 DFS 順序處理節點對。行為等價，僅訪問順序不同。
• 時間複雜度：O(n)，空間複雜度：O(h)

1. 如果將此題改為判斷兩棵不同的樹是否互為鏡像，你的解法需要如何修改？
2. 你能否在不使用遞迴的情況下，以迭代方式解決本題？請說明所需的資料結構。
3. 若輸入是一棵 N 叉樹（每個節點可有任意數量的子節點），對稱的定義應如何延伸，演算法又該如何調整？