Binary Tree Level Order Traversal II
The key idea
Do an ordinary top-down breadth-first sweep, collecting one list per level. The only twist over normal level-order traversal is that the answer wants the levels from the bottom up, so reverse the list of levels (or prepend each new level to the front) at the end.
Problem
Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values — that is, group the node values by depth, then list the groups from the leaf level up to the root, with each level read left to right.
Every node on the same depth belongs to the same level. The last group in the answer is the root's own level [root.val]; the first group is the deepest level of the tree. If the tree is empty (root is null), return an empty list.
Constraints
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Examples
Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]
Input: root = [1]
Output: [[1]]
Input: root = []
Output: []
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM
- Minimum Depth of Binary TreeEASY