題目描述:給定一棵二元樹的根節點 root,判斷此樹是否以根節點為中心左右對稱(即是否為自身的鏡像)。
解題思路:核心觀察是:若一棵樹以中心對稱,則其左子樹與右子樹互為鏡像。我們定義一個輔助函式 isMirror(left, right) 來遞迴判斷兩個子樹是否互為鏡像。
判斷兩個節點 left 和 right 互為鏡像的條件:
null → 對稱(true)null 而另一個不是 → 不對稱(false)false)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)。
1. If root is null, return true (empty tree is symmetric). 2. Call isMirror(root.left, root.right). 3. In isMirror(left, right): a. If both left and right are null, return true. b. If exactly one of them is null, return false. c. If left.val != right.val, return false. d. Return isMirror(left.left, right.right) AND isMirror(left.right, right.left).
方法一:迭代 BFS(使用佇列)
root.left 和 root.right 加入佇列。每輪取出一對節點:若都為 null 則繼續;若一個 null 則回傳 false;若值不同則回傳 false;否則按照鏡像順序將 4 個子節點加入佇列(l.left 配 r.right,l.right 配 r.left)。方法二:迭代 DFS(使用堆疊)