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

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

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

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

測試範例

Example 1:

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