今日題目

題目連結：100. same tree
題目主題：Tree, Depth-First Search, Breadth-First Search, Binary Tree

在練習過Preorder、Inorder、Postorder三種Traversal以後，今天找了一題最後再來練習一下Depth-First Search主題。

簡單說說 Tree Visualizer

雖然在前幾篇都練習過如何把一個陣列看成一棵樹，但這邊可以分享一下，如果今天懶得自己想像Tree的樣子，可以用Leetcode提供的功能來顯示。

如上圖，可以在Testcase的地方，開啟Tree Visualizer，這時候上面就會出現一棵樹的形狀，下方的框框也會有藍色的一條做標示，告訴你現在這棵樹是用哪個陣列形成的。

題目解說

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

題目會給兩棵樹，分別為 p 及 q，目標是檢查這兩棵樹是否所有TreeNode都是一樣的，若都是一樣的回傳True，若不一樣就回傳False。

約束：

• 樹的節點總數範圍在 [0, 100]
• -10的4次方 <= Node.val <= 10的4次方

範例1

輸入: p = [1,2,3], q = [1,2,3]
輸出: true

範例2

輸入: p = [1,2], q = [1,null,2]
輸出: false

範例3

輸入: p = [1,2,1], q = [1,1,2]
輸出: false

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

解題的想像

文字描述

1. 寫一個遞迴方法，這個方法會傳兩棵樹目前要前往的TreeNode。
2. 每次呼叫這個方法，前往的節點兩邊會是同步的。
3. 用Preorder的方式，每進入一個節點直接檢查當下節點是否為相同，檢查的狀態有以下：
   • 目前節點都為空，代表目前都相同，繼續檢查下一個節點
   • 目前節點一個為空、一個不為空，代表兩棵樹已經不同了
   • 目前節點都有值，但值不相同，代表兩棵樹已經不同了
4. 全部節點都走完，並且過程中都沒有出現不同的節點，代表最終兩棵樹是相同長相的樹。

圖解過程

範例: p = [1,2,3], q = [1,2,3]

如上圖，檢查兩棵樹是否一樣，這次是用Preorder Traversal來實作，也就是進入一個節點就檢查，可以看到step1 ~ step4 基本上都是，兩邊的樹 p 跟 q 都是同時在前進的，過程中每一步都會去確認目前兩顆樹的節點是否相同，即便是綠色圓這個路徑的每一步都會確認是否相同，一直到整棵樹都走過一次沒有不一樣，最終就是回傳True。

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

程式碼撰寫

class Solution:
    def sameNode(self, p: TreeNode, q: TreeNode):
        # 目前節點都為空
        if p == None and q == None:
            return True
        # 檢查 兩種狀況都代表樹長的不同
        # 1. 目前節點是否一個為空、一個不為空
        # 2. 兩個都有節點但值不一樣
        if ((p != None and q == None)
         or (p == None and q != None)
         or (p.val != q.val)):
            return False
        # 若已經檢查到有一個節點不相同，直接結束這個遞迴
        if not self.sameNode(p.left, q.left):
            return False
        # 若已經檢查到有一個節點不相同，直接結束這個遞迴
        if not self.sameNode(p.right, q.right):
            return False
        # 節點都相同才會走到這
        return True
    
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        return self.sameNode(p, q)

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

1. Tree Visualizer 的用法
2. 100.same tree 的解題方法

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

Next：965. Univalued Binary Tree