470. Zigzag Floors
A museum is laid out as a binary tree of galleries. The entrance gallery is root, and every gallery opens onto at most one gallery on its left and one on its right, one floor further down. A guided tour visits the museum one floor at a time, beginning with the entrance floor. Guests walk the first floor from left to right, then the next floor from right to left, and the direction keeps alternating on every new floor.
Given root, return a list of lists in which the i-th inner list holds the values of the galleries on floor i (the entrance is floor 0) in the exact order the guests visit them. If root is empty, return an empty list.
Example 1
- Input:
- root = [12,5,19,3,8,null,24,1]
- Output:
- [[12],[19,5],[3,8,24],[1]]
- Explanation:
Even-numbered floors are read left to right and odd-numbered floors right to left, giving [[12],[19,5],[3,8,24],[1]].
Example 2
- Input:
- root = [6,null,14,9]
- Output:
- [[6],[14],[9]]
- Explanation:
Even-numbered floors are read left to right and odd-numbered floors right to left, giving [[6],[14],[9]].
Example 3
- Input:
- root = [31,17,40,11,23,36,52,4]
- Output:
- [[31],[40,17],[11,23,36,52],[4]]
- Explanation:
Even-numbered floors are read left to right and odd-numbered floors right to left, giving [[31],[40,17],[11,23,36,52],[4]].
Constraints
0 ≤ number of nodes ≤ 105
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)