Description
Return tree values grouped by depth, from root downward and left to right.
Solution
from collections import deque
def level_order(root):
queue = deque([root]) if root else deque()
result = []
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[1,2,3,null,4]]- Output
[[1],[2,3],[4]]
Values are grouped by distance from the root.
Example 2
- Input
[[]]- Output
[]
An empty tree has no levels.
Example 3
- Input
[[5]]- Output
[[5]]
The root is the only level.
Approach
Process the current queue length as one level before adding the next level.
Time & space
O(n) time; O(w) auxiliary space plus O(n) output, for maximum width w.