BFS 經典入門題 Binary Tree Level Order Traversal_Leetcode #102

更新於 發佈於 閱讀時間約 3 分鐘
BFS 先天具有 點波源擴散,逐層由內往外探索的特質

BFS 先天具有 點波源擴散,逐層由內往外探索的特質

題目敘述: 102. Binary Tree Level Order Traversal


題目會給定給我們一顆二元樹的根結點,
要求我們輸出Level-order traversal的拜訪結果。


測試範例

Example 1:

raw-image
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

演算法

其實這題就剛好可以套用圖論裡面的BFS廣度優先探索演算法,也呼應之前我們在圖論演算法統整介紹過的概念。

BFS在探索Tree/Binary tree相關的領域中,還有一個名字,叫做Level-order traversal 逐層探索演算法從第一層Root根接點,逐層探索到Leaf葉子節點 也是最深的那一層


複習一下常見的BFS模板:

traversalQ = [startNode]
visited = set()

while traversalQ:
 
 curNode = traversalQ.popleft()
 // do something, or print something
 visited.add( curNode ) 

 for neighbor in graph[curNode]:
  if neighbor not in visited:
   traversalQ.append( neighbor )

程式碼

把BFS廣度優先演算法具象化,實作Binary tree的Level order traversal

class Solution:
 def levelOrder(self, root: TreeNode) -> List[List[int]]:
  
  
  if not root:
   # Quick response for empty tree
   return []
  
  traversalQ, result = deque([root]), []
  
  # level order traversal
  while traversalQ:
   
   # going down level-by-level
   cur_level_trace, cur_level_len = [], len(traversalQ)

   for _ in range(cur_level_len):
    
    cur_node = traversalQ.popleft()
         
    cur_level_trace.append(cur_node.val)
    cur_node.left and traversalQ.append( cur_node.left )
    cur_node.right and traversalQ.append( cur_node.right )
   
   
   result.append( cur_level_trace )
   
  return result

複雜度分析

時間複雜度: O( n )

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

空間複雜度: O( n )

O( n ) 耗費在traversal ququq的空間本,

最長的那一層在最後一層,長度最長為O( n/2 )


Reference

[1] Python/JS/Java/Go/C++ O(n) by BFS [w/ Comment ] — Binary Tree Level Order Traversal — LeetCode

留言
avatar-img
留言分享你的想法!
小松鼠-avatar-img
發文者
2024/09/15
🔯從Python來學圖論Graph 與 BFS廣度優先探索提及了這篇文章,趕快過去看看吧!
avatar-img
小松鼠的演算法樂園
95會員
427內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/26
Leetcode 729. My Calendar I 給定一個行事曆的class定義和行程安排的介面interface。 請完成下列function 1.建構子MyCalendar() 初始化MyCalendar物件 2.boolean book(int start, int end) 插入新行程
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/10
Insert Greatest Common Divisors in Linked List 題目給定一個鏈結串列, 請在兩兩節點之間加入一個新節點,新節點的值為兩者之間的最大公因數。 最後返回新串列的head node作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
2024/09/09
2326. Spiral Matrix IV 題目給定一個Linked list和對應的矩陣高度m、寬度n。 請依照順時針的拜訪順序, 從左上角出發,依照次序把Linked List的內容填到矩陣裡。 如果有剩餘不足的空位,就填補-1。 最後將填補好的矩陣返回作為答案。
Thumbnail
看更多
你可能也想看
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
介紹朋友新開的蝦皮選物店『10樓2選物店』,並分享方格子與蝦皮合作的分潤計畫,註冊流程簡單,0成本、無綁約,推薦給想增加收入的讀者。
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
每年4月、5月都是最多稅要繳的月份,當然大部份的人都是有機會繳到「綜合所得稅」,只是相當相當多人還不知道,原來繳給政府的稅!可以透過一些有活動的銀行信用卡或電子支付來繳,從繳費中賺一點點小確幸!就是賺個1%~2%大家也是很開心的,因為你們把沒回饋變成有回饋,就是用卡的最高境界 所得稅線上申報
Thumbnail
題目敘述 題目會給定我們一顆二元搜索樹BST的根結點, 還有一個指定區間的上邊界R 和 下邊界L。 請問二元搜索樹中,所有落在指定區間內的節點元素值的總和是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,15,3,7,null,18], l
Thumbnail
題目敘述 題目會給定我們一顆二元搜索樹BST的根結點, 還有一個指定區間的上邊界R 和 下邊界L。 請問二元搜索樹中,所有落在指定區間內的節點元素值的總和是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,15,3,7,null,18], l
Thumbnail
題目敘述 題目會給定我們一顆二元搜索樹的根結點root,和任意兩個樹中的節點p和q。 要求我們找出p, q最靠近的公共祖先節點。 題目的原文敘述 測試範例 Example 1: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q
Thumbnail
題目敘述 題目會給定我們一顆二元搜索樹的根結點root,和任意兩個樹中的節點p和q。 要求我們找出p, q最靠近的公共祖先節點。 題目的原文敘述 測試範例 Example 1: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q
Thumbnail
題目會給我們一顆二元樹的根結點,要求我們找出每一層最大的節點值。
Thumbnail
題目會給我們一顆二元樹的根結點,要求我們找出每一層最大的節點值。
Thumbnail
題目會給定給我們一顆二元樹的根結點, 要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
Thumbnail
題目會給定給我們一顆二元樹的根結點, 要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
Thumbnail
題目會給我們一顆二元樹的根節點, 要求我們對齊根節點正中央的虛擬分割線,反轉整顆二元樹。
Thumbnail
題目會給我們一顆二元樹的根節點, 要求我們對齊根節點正中央的虛擬分割線,反轉整顆二元樹。
Thumbnail
題目會給定給我們一顆二元樹的根結點,要求我們輸出Level-order traversal的拜訪結果。 在這題,我們會複習並利用BFS模板,來實現逐層搜索演算法。
Thumbnail
題目會給定給我們一顆二元樹的根結點,要求我們輸出Level-order traversal的拜訪結果。 在這題,我們會複習並利用BFS模板,來實現逐層搜索演算法。
Thumbnail
其實常見的tree traversal (前序、中序、後序拜訪), 背後的核心觀念都是相同的。 Tree traversal其實就是探索整顆樹的搜索空間,也可以說是探索整顆樹, 只是指定順序略有不同而已。 本文將結合經典的DFS模板,做一個全面性的回顧。
Thumbnail
其實常見的tree traversal (前序、中序、後序拜訪), 背後的核心觀念都是相同的。 Tree traversal其實就是探索整顆樹的搜索空間,也可以說是探索整顆樹, 只是指定順序略有不同而已。 本文將結合經典的DFS模板,做一個全面性的回顧。
Thumbnail
題目會給定一顆樹,要求我們輸出所有從Root node根節點 到 Leaf node 葉子節點的路徑。 我們會介紹DFS模板 + Tree search演算法的框架來解題
Thumbnail
題目會給定一顆樹,要求我們輸出所有從Root node根節點 到 Leaf node 葉子節點的路徑。 我們會介紹DFS模板 + Tree search演算法的框架來解題
Thumbnail
Leetcode #101 Symmetric Tree 題目會給定一顆樹,要求我們判定這棵樹是不是左右鏡像對稱(Symmetric)。
Thumbnail
Leetcode #101 Symmetric Tree 題目會給定一顆樹,要求我們判定這棵樹是不是左右鏡像對稱(Symmetric)。
Thumbnail
圖論常用的演算法BFS 與 DFS 的統整與比較。 介紹常用且相關的底層資料結構 並且,介紹幾個適合使用的應用領域、解題分類。
Thumbnail
圖論常用的演算法BFS 與 DFS 的統整與比較。 介紹常用且相關的底層資料結構 並且,介紹幾個適合使用的應用領域、解題分類。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News