今日題目

題目連結：101. Symmetric Tree
題目主題：Tree, Depth-First Search, Breadth-First Search, Binary Tree

簡單說說 Traversal

Traversal 已經在前幾天差不多都提過了，但這邊想再分享一下，其實 Traversal 是可以簡單分為兩種方向，從左節點開始走或從右節點開始走，在前面的文章中都是以左邊節點開始走的範例，今天也在複習一下每一種Traversal的差別，這裡分享一下從左邊及從右邊開始走的運作範例：

假設資料：tree = [5, 2, 6, 1, 3, null, 8]

Preorder Traversal

Inorder Traversal

Postorder Traversal

Levelorder Traversal

這邊特別提一下 Inorder Traversal 有趣的狀況，範例因為剛好是 Binary Search Tree，所以可以發現從左先走會排出一個從小到大的順序 [1, 2, 3, 5, 6, 8]、從右先走會排出一個從大到小的順序 [8, 6, 5 ,3, 2, 1]。如果還不知道什麼是 Binary Search Tree 沒關係， 下一篇將會開始會分享 Binary Search Tree 的主題。

題目解說

建議可以看看LeetCode原本的題目說明，這邊是用我的方式說明題目，參考就好。

題目會給一顆二元樹，目標是確認這棵樹是不是兩邊節點長的一樣的對稱樹，像是照鏡子一樣，參考下面從Leetcode上面截取的範例圖：

如果是一顆對稱樹將會回True，若不是對稱樹則回傳False，下面是從Leetcode上面截取非對稱樹的範例圖：

約束：

• 樹的節點總數範圍在[1, 1000]
• -100 <= Node.val <= 100

範例1

輸入：root = [1,2,2,3,4,4,3]
輸出：true
解說：參考題目解說的第一張圖。

範例2

輸入：root = [1,2,2,null,3,null,3]
輸出：false
解說：參考題目解說的第二張圖。

建議到這邊先停下來，嘗試自己解解看，若沒有想法可再繼續走下去。

解題的想像

文字描述

1. 若根節點沒有子節點，直接回傳True結束
2. 使用Level-Order Traversal來實作
3. 宣告兩個Queue，一個往左邊走，一個往右邊走
4. 跑一個迴圈，直到兩邊都把全部節點走完：
   • 每一圈分別跟兩邊各取一個節點
   • 確認是否兩邊都有節點，若其中一邊沒節點，代表非對稱直接回傳False結束
   • 確認裡面的值是否相同，若不同代表非對稱，直接回傳False結束
   • 若目前都對稱且還有子節點，分別放進兩邊的Queue，繼續迴圈
5. 若全部節點都走完，代表這是一個對稱樹，回傳True

圖解過程

範例：root = [1, 2, 2, 3, 4, 5, 3]

上圖中，一開始我們先宣告兩個Queue，用來實現Level-Order Traversal使用的，因為需要兩邊同時走，所以宣告分別為 leftQueue 及 rightQueue 。若根節點沒有子節點會直接回傳True，可以看到範例是有子節點的，所以兩邊 Queue 直接從第二層節點開始走。

上圖是迴圈的運作過程，橘黃色方框是目前走到的節點，可以看到左邊跟右邊同時會取得一個來確認目前是不是對稱的，確認完會繼續將下層節點放到 Queue 中準備。

可以觀察 step1 ，左邊跟右邊走的方向也會不一樣，左邊是優先走左邊 3 節點在走 4 節點，而右邊是優先走右邊 3 節點在走 5 節點。

最後會在 step3 讀到最後一個節點發現，這不是一顆對稱的樹，左邊節點讀到的是 4，右邊節點讀到的是 5，所以最後這個範例是回傳 False。

若因為沒想法而走到這邊，建議看完想像以後再給自己一次機會試一次。

程式碼撰寫

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        # 若根節點沒有子節點，直接回傳True結束
        if not root.left and not root.right:
            return True
        
        # 使用Level-Order Traversal的方式走
        # 準備兩個Queue，左邊及右邊同時一起走
        leftQueue = deque()
        rightQueue = deque()
        leftQueue.append(root.left)
        rightQueue.append(root.right)
        
        # 若兩邊都走到沒節點，結束這個迴圈
        while len(leftQueue) > 0 and len(rightQueue) > 0:
            # 取出左邊及右邊節點
            left = leftQueue.popleft()
            right = rightQueue.popleft()
            # 其中一個有節點，另一邊沒節點，直接回傳False結束
            if (left and not right) or (right and not left):
                return False
            # 若兩邊都有節點
            if left and right:
                # 確認兩邊值是否不同，不同直接回傳False結束
                if left.val != right.val:
                    return False
                else:
                    # 把子節點放進Queue繼續迴圈
                    leftQueue.append(left.left)
                    leftQueue.append(left.right)
                    rightQueue.append(right.right)
                    rightQueue.append(right.left)
        # 全部走完，代表這是一個對稱樹
        return True

希望您今天能瞭解到...

1. Traversal 左邊走及右邊走的過程
2. 101. Symmetric Tree 的解題方法

若內容有什麼問題或建議歡迎一起交流：）
感謝您今天願意花時間看完這篇文章~~~~

Next：108. Convert Sorted Array to Binary Search Tree