Easy

给定二叉树，返回从下至上层级遍历的节点值(从左往右，从叶到根)

Example:
二叉树 [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回:
[
[15,7],
[9,20],
[3]
]

此题是典型的DFS(depth-first search)算法题。可以使用递归的办法：

1. 根节点level为0，寻找根节点的值，加入响应res

2. 更新根节点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