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] ]
解法
# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def levelOrderBottom(self, root: TreeNode) -> List[List[int]]: if not root: return [] _result=collections.defaultdict(list) #广度遍历 BFS def _bfs(root,level,_result): queue = [[root,1]] while len(queue) > 0: temp,level = queue.pop(0) _result[level].append(temp.val) if temp.left: queue.append([temp.left,level+1]) if temp.right: queue.append([temp.right,level+1]) _bfs(root,1,_result) result=[] for x in sorted(_result.keys(),reverse=True): result.append(_result[x]) return result
上面的代码主要是通过队列实现BFS的访问,使用defaultdict对象保存结果,字典的key是对应每一层的编号,value就是每一层从左到右的排序结果。
下面给出的leetcode讨论区给出的答案,这个完全会更加易懂,实现思想都是基于BFS
class Solution(object): def levelOrderBottom(self, root): """ :type root: TreeNode :rtype: List[List[int]] """ res = [] arr = [] if root is None: return [] else: arr.append(root) while True: tmp = [] while len(arr) > 0: item = arr.pop(0) tmp.append(item) res.insert(0, [w.val for w in tmp]) for item in tmp: if item.left is not None: arr.append(item.left) if item.right is not None: arr.append(item.right) if len(arr) == 0: break return res