1 題目描述

檢查是否對稱。
Follow up: Could you solve it both recursively and iteratively?

2 解法

2.1 Recursioin

一樣套用Recursion的思維，我們先將大問題變成小問題

  1. 大問題：知道一個樹是否對稱
  2. 小問題：讓我們相信遞歸並假設我們已經透過遞歸給出了根的左子樹和右子樹是否對稱。
  3. 大小關係式：(left.val == right.val) and (left.left, right.right) and (left.right, right.left)
    • 當前的值 and 外面對稱 and 裡面對稱
  4. 最小的問題：當 left 和 right 都觸底的時候，是對稱的，但是當其中一邊有值，另一邊沒有值，就不對稱了。

我們可以定義一個遞歸函數，它將兩個節點作為輸入，一個來自左子樹，一個來自右子樹。如果兩個節點都為 null，或者它們的值相等且子樹對稱，則輔助函數傳回 true。

大概是這樣的感覺：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if root is None:
            return True

        return self._is_symmetric(root.left, root.right)

    def _is_symmetric(self, left_root: TreeNode, right_root: TreeNode) -> bool:
        if left_root is None and right_root is None:
            return True
        if left_root is None or right_root is None:
            return False

        outside = self._is_symmetric(left_root.left, right_root.right)
        inside = self._is_symmetric(left_root.right, right_root.left)

        return left_root.val == right_root.val and outside and inside

2.2 Iteration

  1. 初始化隊列：將根節點的左子樹和右子樹成對放入隊列中。
  2. 迭代檢查：
    1. 每次從隊列中取出一對節點進行比較。
    2. 如果兩個節點都為 None，則繼續下一次迭代。
    3. 如果其中一個節點為 None 或兩個節點的值不相等，則樹不對稱，返回 False。
    4. 將節點的子節點成對放入隊列中，以便在下一次迭代中檢查：
      1. inside: 左節點的右子樹與右節點的左子樹成對。
      2. outside: 左節點的左子樹與右節點的右子樹成對。
  3. 結束條件：當隊列為空時，表示已經檢查完所有成對的節點，且都對稱，返回 True。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import deque

def isSymmetric(self, root: Optional[TreeNode]) -> None:
    if root is None: 
        return True 
    # 初始化隊列 成對放入
    queue = deque((root.left, root.right))

    while queue: 
        left, right = queue.popleft()
        if left is None and right is None: 
            continue
        if left is None or right is None or left.val != right.val: 
            return False

        queue.append((left.left, right.right))
        queue.append((left.right, right.left))
    
    return True

3 總結

就差一點點，我還是有偷看解答的前面兩段話獲得hint，差點寫除來，但是很接近了。最後我卡在 left_root.val == right_root.val and outside and inside 一開始我只有意識到 outside and inside，我是把 left_root.val == right_root.val 當作最小問題來處理，但他還不是最小。最小問題是雙方為None時。