Binary Tree Level Order Traversal II

Question

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example: 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]
]

Tags

• Tree
• BFS

Thought

Almost the same as the previous problem. Thus, the most simple idea is to use the solution in the previous problem and reverse the result before return it.

Code

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

class Solution(object):
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        result = []
        if root is None:
            return result
        queue = [(0, root)]
        while queue:
            level, ptr = queue.pop(0)
            if ptr.left is not None:
                queue.append((level + 1, ptr.left))
            if ptr.right is not None:
                queue.append((level + 1, ptr.right))
            if len(result) == level:
                result.append([ptr.val])
            else:
                result[level] += [ptr.val]
        result.reverse()
        return result