BFS 經典入門題 Binary Tree Level Order Traversal II Leetcode #107

這題的題目在這

測試範例:

Example 1:

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

Example 2:

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

Example 3:

Input: root = []
Output: []

約束條件:

Constraints:

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

演算法:

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

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

唯一的差別是，這題要求的是上下顛倒的順序。

所以，我們只要套用前一題的演算法，最後把結果做反向，再輸出，就滿足題目所求。

這種演算法化簡的技巧，在演算法理論也稱之為Reduction，

把一個新的問題A，映射到一個已經知道解法(演算法)的問題B，再透過已知問題B的解答反推問題A的答案。

程式碼:

class Solution:
　def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
　
　　def levelOrder(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)
　　　　　if cur_node.left: traversalQ.append( cur_node.left )
　　　　　if cur_node.right: traversalQ.append( cur_node.right )


　　　　result.append( cur_level_trace )

　　　return result
　　
　　#-----------------------------------
　　
　　# Reduce to Leetcode #102 Binary tree level order traversal
　　
　　return levelOrder(root)[::-1]

時間複雜度:

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

空間複雜度:

O( n ) 最深的那一層在最後一層，最長為O( n/2 )

[1] Python/Java/JS/C++/Go by normal traversal // Reduction [w/Hint] — Binary Tree Level Order Traversal II — LeetCode