基礎圖論題目 Symmetric Tree Leetcode #101

閱讀時間約 5 分鐘
raw-image

這題題目在這裡:

題目會給定一顆樹,要求我們判定這棵樹是不是左右鏡像對稱(Symmetric)。


測試範例:

Example 1:

raw-image
Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

raw-image
Input: root = [1,2,2,null,3,null,3]
Output: false

約束條件:

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?


演算法:

使用到的技巧和前一題Same Tree類似。

這題一樣可以用DFS或是BFS來解,剛好呼應Follow-up 的Recursive遞迴解和 Iterative 迭代解。

範例一的暗示已經很清楚,就是假想樹的正中間有一條虛擬的分割線,把樹拆成左右兩顆子樹,判斷左子樹、右子樹是否以分割線為對稱軸,左右鏡像對稱

DFS、BFS的核心觀念一樣依循同樣的原則:

若左、右子樹皆非空,則判斷當下節點值是否相同,並且用同樣的邏輯去判斷下一層的子樹,在DFS裡面就是遞迴呼叫,在BFS裡面就是推入對應成雙成對鏡像的節點


DFS程式碼:

class Solution:

 def check_symm(self, p:TreeNode, q:TreeNode)->bool:
  
  # Stop condition
  if not(p and q):
   return p == q
  
  # General case:
  # both p and q exist, check symmetry on both child nodes
  return p.val == q.val and self.check_symm( p.left, q.right) and self.check_symm( p.right, q.left)
  
 
 def isSymmetric(self, root: TreeNode) -> bool:
  
  if root is None:
   # empty tree
   return True
  else:
   # check symmetry by function check_symm
   return self.check_symm( root.left, root.right)

時間複雜度:

O( n ) 每個節點至多拜訪一次。

空間複雜度:

O( n ) 樹高最深為O(n),當這顆樹為向左歪斜,或者向右歪斜的時候。


BFS程式碼:

class Solution:

 def isSymmetric(self, root: TreeNode) -> bool:
  
  traversal_queue = deque( [root, root] )

  while traversal_queue:

   # Left half
   L = traversal_queue.popleft()

   # Right half
   R = traversal_queue.popleft()

   # Both Left and Right are empty, i.e., NULL node
   if (not L) and (not R): continue

   # Either L or R is empty, or
   # L's value is not equal to R's value
   if (not L) or (not R) or ( L.val != R.val):
    return False
   
   # Keep compare Left subtree and Right subtree with symmetry judgement
   traversal_queue.append(L.right)
   traversal_queue.append(R.left)
   
   traversal_queue.append(R.right)
   traversal_queue.append(L.left)

  return True

時間複雜度:

O( n ) 每個節點至多拜訪一次。

空間複雜度:

O( n ) 佇列最長為O(n),每個節點最多推入佇列一次,從佇列取出一次。


Reference:

[1] Python O( n ) by DFS and BFS. 87%+ [w/ Visualization] — Symmetric Tree — LeetCode




84會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
圖論常用的演算法BFS 與 DFS 的統整與比較。 介紹常用且相關的底層資料結構 並且,介紹幾個適合使用的應用領域、解題分類。
Leetcode #100: Same Tree 題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。 也就是說,形狀相同,節點的數值也相同。
進階圖論題目: 計算最短的一筆畫路徑長 題目會給定我們一張圖和對應的相鄰矩陣,要求我們返回一筆畫拜訪所有節點的最短路徑長,起終點不拘。
Coin Change + DP 策略_Leetcode 面試題 上機考 題目 詳細解說
圖論常用的演算法BFS 與 DFS 的統整與比較。 介紹常用且相關的底層資料結構 並且,介紹幾個適合使用的應用領域、解題分類。
Leetcode #100: Same Tree 題目會給定兩棵Binary Tree的根結點,要求我們判斷兩棵樹是否一模一樣。 也就是說,形狀相同,節點的數值也相同。
進階圖論題目: 計算最短的一筆畫路徑長 題目會給定我們一張圖和對應的相鄰矩陣,要求我們返回一筆畫拜訪所有節點的最短路徑長,起終點不拘。
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)解法都一次呈現在一張圖上,甚至還能用在軟性的生活溝通上。