# Definition for a  binary tree node

# class TreeNode:

#     def __init__(self, x):

#         self.val = x

#         self.left = None

#         self.right = None

class Solution:

    # @param root, a tree node

    # @return a list of lists of integers

    def levelOrderBottom(self, root):

        """

        BFS from root, and record the values level by level

        """

        # List of levels

        res = []

        # Special case: empty tree

        if not root:

            return res

        level = [root]

        while level:

            temp = []

            res.insert(0, [n.val for n in level])

            for node in level:

                if node.left:

                    temp.append(node.left)

                if node.right:

                    temp.append(node.right)

            level = temp

        # Return

        return res