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
