/107. Binary Tree Level Order Traversal II

107. Binary Tree Level Order Traversal II

Medium
Trees67.8% acceptance

Given a binary tree represented by its root node, return a list of lists containing the node values in bottom-up level order traversal. Each inner list contains the values of nodes at a particular depth, ordered from left to right. The outer list should be ordered from the deepest level to the root.

Example 1

Input: TreeNode(5, TreeNode(2), TreeNode(8, TreeNode(7), TreeNode(10)))

Output: [[7,10],[2,8],[5]]

Explanation: Level 2: [7,10], Level 1: [2,8], Level 0: [5]

Example 2

Input: TreeNode(4, None, TreeNode(6, TreeNode(5), None))

Output: [[5],[6],[4]]

Explanation: Level 2: [5], Level 1: [6], Level 0: [4]

Example 3

Input: None

Output: []

Explanation: Empty tree returns empty list.

Constraints

  • 0 <= number of nodes <= 2000
  • -1000 <= node value <= 1000
Python (current runtime)

Case 1

Input: TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))

Expected: [[4],[2,3],[1]]

Case 2

Input: TreeNode(9)

Expected: [[9]]

Case 3

Input: TreeNode(7, TreeNode(3, None, TreeNode(5)), TreeNode(8))

Expected: [[5],[3,8],[7]]