107. Binary Tree Level Order Traversal II

Information

  • Diffculty: Easy

  • Created: 2017-11-10 15:23:24

  • Last Motified: 2020-01-09 22:53:34

  • Tags: Tree, Breadth-first Search

Intuition

For this problem, we need to use BFS to get nodes in each level.

Solution

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


class Solution:
    def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        queue = deque([[root, 0]])
        levelorder = []
        while queue:
            node, level = queue.popleft()
            if node is None:
                continue
            if len(levelorder) <= level:
                levelorder.append([])
            levelorder[level].append(node.val)
            queue.append([node.left, level + 1])
            queue.append([node.right, level + 1])
        levelorder.reverse()
        return levelorder