Easy
给定二叉树，返回从下至上层级遍历的节点值(从左往右，从叶到根)
Example:
二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回:
[
[15,7],
[9,20],
[3]
]
此题是典型的DFS(depth-first search)算法题。可以使用递归的办法：
- 根节点level为0，寻找根节点的值，加入响应res
- 更新根节点level，对根节点的左分支和右分支分别找根节点。
这里的关键是通过根节点的level来控制左右往下遍历的时能够同步推进。因为此题要从下往上输出，需要对结果进行reverse。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def levelOrderBottom(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
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)
dfs+stack
下面是另外一种解决方案，直接利用stack。
def levelOrderBottom2(self, root):
stack = [(root, 0)]
res = []
while stack:
node, level = stack.pop()
if node:
if len(res) < level+1:
res.insert(0, [])
res[-(level+1)].append(node.val)
stack.append((node.right, level+1))
stack.append((node.left, level+1))
return res
bfs + queue
下面是第三者解决办法，利用queue。
def levelOrderBottom(self, root):
queue, res = collections.deque([(root, 0)]), []
while queue:
node, level = queue.popleft()
if node:
if len(res) < level+1:
res.insert(0, [])
res[-(level+1)].append(node.val)
queue.append((node.left, level+1))
queue.append((node.right, level+1))
return res
