原題鏈接https://leetcode.com/problems/binary-tree-level-order-traversal-ii/
Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
return its bottom-up level order traversal as:
[
[15,7],
[9,20],
[3]
]
基本與該題解題方法一樣，都是層序遍歷，只是本題從底層開始輸出燃领，本來準(zhǔn)備從頂層輸出到棧丸逸，然后出棧到list，所以用res_stack命名了儒恋。后來直接用list[::-1]求解了善绎，也可以雙端隊列從左邊加入隊列。
from collections import deque
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
if not root:
return []
deques = deque()
res_stack = []
# res_stack = deque()
deques.append(root)
count = 1
while deques:
res = []
n = count
count = 0
i = 0
while i < n:
item = deques.popleft()
res.append(item.val)
i += 1
if item.left:
count += 1
deques.append(item.left)
if item.right:
count += 1
deques.append(item.right)
res_stack.append(res)
# res_stack.appendleft(res)
return res_stack[::-1]
# return res_stack
