TreeNode(val, left=None, right=None) is in the starter. Keep it.
Implement level_order(root) -> list[list[int]]: the node values grouped by depth. The root's level comes first, and each level lists its values from left to right. An empty tree gives [].
# 4
# / \
# 9 2
# / \
# 6 1
level_order(root) # [[4], [9, 2], [6, 1]]
The tree has up to 131,071 nodes. Aim for O(n) time.
Show hint
Visit nodes in the order of their distance from the root using a FIFO queue (collections.deque; list.pop(0) is O(n) per pop). To know where one level ends, look at how many nodes the queue holds when a level starts.