Q107 Binary Tree Level Order Traversal II

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:
[
  [15,7],
  [9,20],
  [3]
]

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if root == None:
            return []
        rlist = [] # 返回列表
        queue = [] # 模拟队列
        level = 1  # 结点所在层数
        queue.append((root, level))  # 队列的每一个元素存储的是结点地址以及该节点所在层数
        while queue:  # 当队列非空
            node, level = queue.pop(0)  # 从队列中取出一个元素，注意 pop(0)，如果没有0则是从后面取数，而不是队列的操作
            if node != None:  # 如果结点地址不为空
                if len(rlist) < level:  # 如果返回列表的个数小于当前结点的层数，则需要增加一个新列表
                    rlist.insert(0, [])
                rlist[0].append(node.val) # 因为新增的列表插入的位置总是在第一个，所以使用 rlist[0]
                # 把当前结点的左右孩子的地址以及左右孩子所在的层数加入到新的队列中
                queue.append((node.left, level + 1))  
                queue.append((node.right, level + 1))
        return rlist