基礎圖論題目 Same Tree_Leetcode #100

閱讀時間約 2 分鐘
raw-image

題目敘述: 100. Same Tree


題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣

也就是說,形狀相同節點的數值也相同。


測試範例:

Example 1:

raw-image
Input: p = [1,2,3], q = [1,2,3]
Output: true

Example 2:

raw-image
Input: p = [1,2], q = [1,null,2]
Output: false

Example 3:

raw-image
Input: p = [1,2,1], q = [1,1,2]
Output: false

演算法:

圖論中常見的DFS深度優先探索,或BFS廣度優先探索都可以拿來解這一題。

直覺度簡潔度來說,DFS更直覺也更乾淨俐落。


先複習一下DFS的通用模板:

def dfs( parameter ):
 
 # 終止條件
 if stop conidtion:
  return result
 
 # 通則 general cases
 dfs( paramater updated )
 return result

通則:

若p和q同時存在,則檢查p 和 q 的節點數值是否相等,並且用同樣的邏輯,遞迴檢查p, q的左子樹,和p, q的右子樹是否相等。

終止條件:

若p和q不是同時存在,則檢查是否 p == q 而且都等於 NULL。

若兩者皆為空Null,則返回True。

若否,則返回False。


程式碼:

class Solution:
  def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:

  # stop condition
  if not( p and q ):
    return p == q

  # general case:
  return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)



複雜度分析

時間複雜度:

O(n) 每個節點至多拜訪一次,最多就是拜訪整棵樹。

空間複雜度:

O(n) 成本耗費在call stack,當輸入的兩棵樹都向左歪斜,或向右歪斜時,深度最深,最多為O(n)。


Reference:

[1] Python/JS/Go/C++ O(n) sol by DFS [w/ Visualization ] — Same Tree — LeetCode

84會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
進階圖論題目: 計算最短的一筆畫路徑長 題目會給定我們一張圖和對應的相鄰矩陣,要求我們返回一筆畫拜訪所有節點的最短路徑長,起終點不拘。
Coin Change + DP 策略_Leetcode 面試題 上機考 題目 詳細解說
進階圖論題目: 計算最短的一筆畫路徑長 題目會給定我們一張圖和對應的相鄰矩陣,要求我們返回一筆畫拜訪所有節點的最短路徑長,起終點不拘。
Coin Change + DP 策略_Leetcode 面試題 上機考 題目 詳細解說
你可能也想看
Google News 追蹤
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
靈魂藍圖是以「靈魂」的角度來洞察這一世的計畫,透過有系統和架構的切入方式,你會更清楚自己的挑戰、潛能和目標,也會更明白自己的使命、方向和熱情所在。
Thumbnail
  歡迎各位回到Life Architect.這是非官方的人類圖培訓機構,希望對人類圖有興趣的朋友能突破傳統人類圖的局限性,在綜合世界各地不同人類圖學派視角的情況下,能有更開闊的視野,以及展現出更多生命不同的可能性.   這次的人類圖基礎課上,我們會談談人類圖的非我是什么.傳統人類圖都傾向
Thumbnail
題目會給定一顆樹,要求我們輸出所有從Root node根節點 到 Leaf node 葉子節點的路徑。 我們會介紹DFS模板 + Tree search演算法的框架來解題
Thumbnail
Leetcode #101 Symmetric Tree 題目會給定一顆樹,要求我們判定這棵樹是不是左右鏡像對稱(Symmetric)。
Thumbnail
Leetcode #100: Same Tree 題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。 也就是說,形狀相同,節點的數值也相同。
Thumbnail
先教一下大家如何繪製生命密碼圖,利用該圖可以知道自己的組成。 首先,要知道我們的數字只有1~9,當我們的總和超過時,必須將十位數數字和各位數字加總,比如為12,則為1+2=3,數字則為3,知道之後,依下表填入自己的出生年月日。
Thumbnail
本篇要來講述兩個很少用,而且也會讓人很困惑的小功能,塗鴉(Sketch)與局部塗鴉(Inpaint Sketch)。
Thumbnail
這一篇要來敘述Stable Diffusion的Automatic1111的圖生圖(img2img,簡稱i2i)功能。
Thumbnail
這一篇要開始來敘述Stable Diffusion的Automatic1111的基礎功能。 一切都要先從最基本的文生圖(txt2img)開始。這是Automatic1111開啟之後的第一個頁面,也是最常用最重要的功能。
Thumbnail
我喜歡的圖解力教練 - 邱奕霖老師要開公開課啦,名稱是《給專業工作者的知識圖解鍊金術》!「圖解」是一種神奇又實用的技能,不但能讓聽者容易懂,還能邀請對方一起動腦想辦法。讓 (1)問題 (2)思考(3)解法都一次呈現在一張圖上,甚至還能用在軟性的生活溝通上。
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
Thumbnail
靈魂藍圖是以「靈魂」的角度來洞察這一世的計畫,透過有系統和架構的切入方式,你會更清楚自己的挑戰、潛能和目標,也會更明白自己的使命、方向和熱情所在。
Thumbnail
  歡迎各位回到Life Architect.這是非官方的人類圖培訓機構,希望對人類圖有興趣的朋友能突破傳統人類圖的局限性,在綜合世界各地不同人類圖學派視角的情況下,能有更開闊的視野,以及展現出更多生命不同的可能性.   這次的人類圖基礎課上,我們會談談人類圖的非我是什么.傳統人類圖都傾向
Thumbnail
題目會給定一顆樹,要求我們輸出所有從Root node根節點 到 Leaf node 葉子節點的路徑。 我們會介紹DFS模板 + Tree search演算法的框架來解題
Thumbnail
Leetcode #101 Symmetric Tree 題目會給定一顆樹,要求我們判定這棵樹是不是左右鏡像對稱(Symmetric)。
Thumbnail
Leetcode #100: Same Tree 題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。 也就是說,形狀相同,節點的數值也相同。
Thumbnail
先教一下大家如何繪製生命密碼圖,利用該圖可以知道自己的組成。 首先,要知道我們的數字只有1~9,當我們的總和超過時,必須將十位數數字和各位數字加總,比如為12,則為1+2=3,數字則為3,知道之後,依下表填入自己的出生年月日。
Thumbnail
本篇要來講述兩個很少用,而且也會讓人很困惑的小功能,塗鴉(Sketch)與局部塗鴉(Inpaint Sketch)。
Thumbnail
這一篇要來敘述Stable Diffusion的Automatic1111的圖生圖(img2img,簡稱i2i)功能。
Thumbnail
這一篇要開始來敘述Stable Diffusion的Automatic1111的基礎功能。 一切都要先從最基本的文生圖(txt2img)開始。這是Automatic1111開啟之後的第一個頁面,也是最常用最重要的功能。
Thumbnail
我喜歡的圖解力教練 - 邱奕霖老師要開公開課啦,名稱是《給專業工作者的知識圖解鍊金術》!「圖解」是一種神奇又實用的技能,不但能讓聽者容易懂,還能邀請對方一起動腦想辦法。讓 (1)問題 (2)思考(3)解法都一次呈現在一張圖上,甚至還能用在軟性的生活溝通上。