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]
]
方法1：bfs
class Solution(object):
def levelOrderBottom(self, root):
res,level,l= [],[[root]],[root]
if not root:
return res
while level and l:
l = [(node.left,node.right) for node in l]
l = [v for lr in l for v in lr if v]
if l:
level.append(l)
while level:
l = level.pop()
r = [node.val for node in l]
res.append(r)
return res
方法2：bfs
class Solution(object):
def levelOrderBottom(self, root):
res,level = [],[root]
while root and level:
res.append([node.val for node in level])
lr = [(node.left,node.right) for node in level]
level = [node for p in lr for node in p if node]
res = [node for node in res[::-1]]
return res
方法3：dfs，递归
class Solution(object):
def levelOrderBottom(self, root):
res = []
self.dfs(root,0,res)
return res def dfs(self,root,level,res):
if root:
if len(res)<level+1:
res.insert(0,[])
res[-(level+1)].append(root.val)
self.dfs(root.left,level+1,res)
self.dfs(root.right,level+1,res)
方法4：dfs,非递归
class Solution(object):
def levelOrderBottom(self, root):
res = []
stack = [(0,root)]
while stack:
level,node = stack.pop()
if node:
if len(res) < level+1:
res.insert(0,[])
res[-(level+1)].append(node.val)
stack.append((level+1,node.right))
stack.append((level+1,node.left))
return res