Serpentine Floor Walk
MediumTrees
Problem
A cleaning robot sweeps a building modelled as a binary tree one floor at a time. It reads the first floor left to right, the second right to left, the third left to right again, and so on.
Given the root, return the values grouped by floor in the order the robot visits them.
Example 1
- Input:
- root = [3, 9, 20, null, null, 15, 7]
- Output:
- [[3], [20, 9], [15, 7]]
Floor 2 is read right to left.
Example 2
- Input:
- root = [1, 2, 3, 4, 5, 6, 7]
- Output:
- [[1], [3, 2], [4, 5, 6, 7]]
Constraints
- 0 ≤ number of nodes ≤ 10^4
- -100 ≤ node.val ≤ 100
Hint
Show the first hint
Start from an ordinary floor-by-floor traversal. What changes between floors?
Walkthrough
How to approach it
01Clarify before coding
- Is the first floor left to right? Yes, then it alternates.
- Empty tree? Return [].
- Should the output be per floor? Yes, a list of lists.
02Brute force
Try to change the traversal itself, e.g. by enqueueing children right-first on odd floors.
Cost: Still O(n), but it is easy to get wrong: flipping the enqueue order scrambles the next floor rather than reversing it.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.