[leetcode tree]107. 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],

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]
方法1：bfs

 1 class Solution(object):
 2     def levelOrderBottom(self, root):
 3         res,level,l= [],[[root]],[root]
 4         if not root:
 5             return res
 6         while level and l:
 7             l = [(node.left,node.right) for node in l]
 8             l = [v for lr in l for v in lr if v]
 9             if l:
10                 level.append(l)
11         while level:
12             l = level.pop()
13             r = [node.val for node in l]
14             res.append(r)
15         return res

方法2：bfs

1 class Solution(object):
2     def levelOrderBottom(self, root):
3         res,level = [],[root]
4         while root and level:
5             res.append([node.val for node in level])
6             lr = [(node.left,node.right) for node in level]
7             level = [node for p in lr for node in p if node]
8         res = [node for node in res[::-1]]
9         return res

方法3：dfs，递归

 1 class Solution(object):
 2     def levelOrderBottom(self, root):
 3         res = []
 4         self.dfs(root,0,res)
 5         return res
 6         
 7     def dfs(self,root,level,res):
 8         if root:
 9             if len(res)<level+1:
10                 res.insert(0,[])
11             res[-(level+1)].append(root.val)
12             self.dfs(root.left,level+1,res)
13             self.dfs(root.right,level+1,res)

方法4：dfs,非递归

 1 class Solution(object):
 2     def levelOrderBottom(self, root):
 3         res = []
 4         stack = [(0,root)]
 5         while stack:
 6             level,node = stack.pop()
 7             if node:
 8                 if len(res) < level+1:
 9                     res.insert(0,[])
10                 res[-(level+1)].append(node.val)
11                 stack.append((level+1,node.right))
12                 stack.append((level+1,node.left))
13         return res

[leetcode tree]107. Binary Tree Level Order Traversal II

相关推荐