0101. Symmetric Tree - chasel2361/leetcode GitHub Wiki

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree [1,2,2,3,4,4,3] is symmetric.
But the following [1,2,2,null,3,null,3] is not.
Note:
Bonus points if you could solve it both recursively and iteratively.

這個題目跟上次確認兩棵二元樹是否相同的題目有點類似，只是這次要處理同一棵樹的左右子樹

對稱需要滿足的條件有以下三個，而根存在與否，並不影響對稱：

1. 左子樹根值 = 右子樹根值
2. 左子樹的左子樹與右子樹的右子樹對稱
3. 左子樹的右子樹與右子樹的左子樹對稱

由此可以用遞迴法寫出以下程式碼：

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        return self.isSym(root.left, root.right)
            
    def isSym(self, l, r):
        if not l and not r: return True
        if (not l and r) or (not r and l): return False        
        return l.val == r.val and self.isSym(l.left, r.right) and self.isSym(l.right, r.left)

---

如果要用迭代法解的話，需要用到 quene (隊列/佇列) 這種資料結構， quene 的特性是先進先出，在 python 裡面可以使用 deque 物件來實現，加入物件使用 deque.append() ；提出物件使用 deque.popleft() 。

我們可以利用 quene 把還沒檢查到的子樹組存起來，需要判斷時再拿出來比對。

完成的程式碼如下：

[1] 先判斷根是否存在，若否就直接回傳 True
[2] 把左子樹及右子樹放入 quene 中
[3] 若左右子樹根皆不存在，表示這個分支對稱，繼續檢查
[4] 若左右子樹根皆存在且值相同，將左子樹的左子樹與右子樹的右子樹作為一個單位放入 quene 、左子樹的右子樹與右子樹的左子樹作為一個單位放入 quene。

from collections import deque
class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True  # [1]
        quene = deque([(root.left, root.right)])  # [2]
        while quene:
            l, r = quene.popleft()
            if not l and not r: continue  # [3]
            if l and r and l.val == r.val:  # [4]
                quene.append((l.left, r.right))
                quene.append((l.right, r.left))
            else:
                return False
        return True

這兩個方法的時間以及空間複雜度並無差別

時間複雜度是 O(N)， 空間複雜度為 O(N)