Skip to main content

Binary Tree Level Order Traversal II

Question​

What is the most efficient algorithm for traversing a binary tree in level order, such that each level's nodes are traversed in order from right to left?

Example 1
Tree: 
     3
   /   \
  9    20
      /  \
    15    7

Result: [[15,7], [9,20], [3]]

Solution​

all//Binary Tree Level Order Traversal II.py
import collections

# Definition for a binary tree node
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrderBottom(self, root):
        if root is None:
            return []
        queue = collections.deque([root])
        ans = []
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            ans.append(level)
        return ans[::-1]