這題的題目在這
題目會給定給我們一顆二元樹的根結點，要求我們輸出上下顛倒的Level-order traversal的拜訪結果。
(基本上，就是前一題的小改版。 XD)測試範例:
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 )
