iT邦幫忙

2021 iThome 鐵人賽

DAY 27
0
Software Development

我在刷LeetCode時邂逅了Python系列 第 27

Day 27:572. Subtree of Another Tree

今日題目

題目連結:572. Subtree of Another Tree
題目主題:Tree, Depth-First Search, String Mathcing, Binary Tree, Hash Function

講完幾個常見的演算法主題以後,這兩天會開始分享 Hash 相關的主題。


簡單說說 Hash Function

我認為 Hash 的核心概念是簡化一個複雜的資料,讓資料有更好的效能處理問題,這個簡化不管是將資料變成數字或是字串都是有可能的。

另外有兩個重點:

  • Hash 過後得到的值是有可能遇到碰撞的問題,也就是說兩個不一樣的資料 Hash 過後卻得到相同的值,這樣就是所謂的碰撞,在設計 Hash Function 時需要特別小心。
  • Hash 過後得到的值,在不知道 Hash Function 邏輯的狀況下,理論上是很難推回到原本資料的長相。

題目解說

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

題目會給兩個 Binary Tree 分別為 root 及 subRoot,如果 subRoot 有出現在 root 之中並且結構及節點值都相同,回傳 True,不符合條件回傳 False。

約束:

  • root 的節點總數範圍在[1, 2000].
  • subRoot 的節點總數範圍在 [1, 1000].
  • -10的4次方 <= root.val <= 10的4次方
  • -10的4次方 <= subRoot.val <= 10的4次方

範例1

https://ithelp.ithome.com.tw/upload/images/20211011/20141336NyVzEFWiuJ.png

輸入: root = [3,4,5,1,2], subRoot = [4,1,2]
輸出: true
解說: 上圖是LeetCode提供的範例圖,很明顯可以看到 subRoot 有出現在 root 裏面且結構及節點值都相同。

範例2

https://ithelp.ithome.com.tw/upload/images/20211011/20141336b0gnDJZ250.png

輸入: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
輸出: false
解說: 上圖是LeetCode提供的範例圖,雖然看得到 [4, 1, 2] 有出現在 root 之中,但最終輸出為 false 的原因是 2 節點的結構並不相同,root 這邊多 2 出現了子節點。

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


解題的想像

文字描述

  1. 寫一個方法將樹轉成字串。
  2. 將題目給的 root 及 subRoot 轉成字串。
  3. 若 subRoot 的字串有出現在 root 的字串中,代表這顆 subRoot 的樹有出現在 root 中,回True,相反的沒出現就回 False。

圖解過程

範例:
root = [5, 4, 1, 7, 2]
subRoot = [4, 7, 2]

https://ithelp.ithome.com.tw/upload/images/20211011/20141336stKxovCBzn.png

上圖是過程中,分別會先將 root 及 subRoot 這兩個複雜的樹簡化成一個字串,之後便可以直接用這兩個字串比對出subRoot 是否有出現在 root 中,以這個範例來說是有比對到 subRoot 轉成的字串是有出現在 root 字串之中的紅色底線部份,因此會回傳 True。

這個樹轉換成字串的過程,是運用了Preorder、Inorder、Postorder的方式組成的字串,每個數字至少會被經過三次,這樣可以確認到結構的長相。

上圖中,黑色數字是Preorder經過時紀錄的、紅色數字是Inorder經過時紀錄的、綠色數字就是Postorder經過的,這樣轉換出來的字串便可完整的去確認 root 中是否有出現跟 subRoot 結構及節點值都相同的樹。

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


程式碼撰寫

class Solution:
    def convertString(self, root, rootStr = ''):
        if root == None: return rootStr
        
        rootStr += str(root.val)
        rootStr = self.convertString(root.left, rootStr)
        rootStr += str(root.val)
        rootStr = self.convertString(root.right, rootStr)
        rootStr += str(root.val)
        
        return rootStr
        
    
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        subRootStr = self.convertString(subRoot)
        rootStr = self.convertString(root)
        
        return subRootStr in rootStr

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

  1. Hash Function 的基本概念
  2. 572. Subtree of Another Tree 的解題方法

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

Next:1. Two Sum


上一篇
Day 26:53. Maximum Subarray (2)
下一篇
Day 28:1. Two Sum
系列文
我在刷LeetCode時邂逅了Python30

尚未有邦友留言

立即登入留言