层次遍历二叉树，并从下往上按层输出

方法1 广搜

用栈实现广搜，每次将层次遍历的结果插入res的头部即可

class Solution1:
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root == None:
            return  []
        res = []
        from collections import deque
        queue = deque()
        queue.append(root)
        while(len(queue)):
            length = len(queue)
            tmp = []
            for i in range(length):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.insert(0,tmp)
        return res

方法2 深搜递归

深搜递归法，参数包括当前的深度，用深度对应res中的位置，当res的长度小于当前的深度时，要在res的头部添加[]

class Solution2:
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        self.res = []
        self.DFS(root, 1)
        return self.res

    def DFS(self, root, level):
        if root == None:
            return
        else:
            if len(self.res) < level:
                self.res.insert(0,[])
                self.res[len(self.res) - level].append(root.val)
            self.DFS(root.left, level+1)
            self.DFS(root.right, level+1)

深搜非递归法

用栈实现，栈中保存节点和当前的深度
入栈的时候要先入右节点，再入左节点

class Solution3:
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        res = []
        if root == None:
            return  res
        stack = [[root,1]]
        while(len(stack)):
            node,depth = stack.pop()
            if len(res) < depth:
                res.insert(0,[])
            res[len(res) - depth].append(node.val)
            if node.left:
                stack.append([node.left, depth+1])
            if node.right:
                stack.append([node.right, depth+1])
        return res