107.Binary Tree Level Order Traversal II

 

# 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: TreeNode) -> List[List[int]]:
        if root == None:
            return []
        queue = [root]
        last = root
        ans = [[root.val]]
        ans_level = []
        while queue:
            node = queue[0]
            queue = queue[1:]
            if node.left :
                queue.append(node.left)
                ans_level.append(node.left.val)
            if node.right:
                queue.append(node.right)
                ans_level.append(node.right.val)
            if node == last:
                if ans_level:
                    ans.append(ans_level)
                    ans_level = []
                if queue:
                    last = queue[-1]
        return ans[::-1]