五. 二叉树 5 Binary Tree Level Order Traversal II

思路：通过BFS（queue的应用）遍历每一层，将每一层作为一个数组存放在另一个数组里。

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""


class Solution:
    """
    @param: root: A tree
    @return: buttom-up level order a list of lists of integer
    """
    def levelOrderBottom(self, root):
        # write your code here
        stack = []
        level = []
        queue = []
        if root:
            queue.append(root)
        else:
            return stack
        while len(queue):
            size = len(queue)
            for i in range(0,size):
                node = queue.pop(0)
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right: 
                    queue.append(node.right)             
               
            stack.insert(0, level)
            level = []
        return stack