The problem
Return a tree’s values level by level, but from the bottom level up.
Input: [3, 9, 20, null, null, 15, 7] Output: [[15, 7], [9, 20], [3]]
Picture it
Picture listing a family by generation, youngest first. Do a normal level-by-level walk, then reverse the list of rows.
Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.
The key idea
BFS by level, then reverse. O(n).
Python solution
def level_order(root):
if not root:
return []
q, out = deque([root]), []
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
out.append(level)
return out[::-1]LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.