Почему это работает
- Очередь никогда не разворачиваем: потомков всегда кладём начиная с левого, поэтому каждый уровень выходит из неё слева направо, как в обычном обходе по уровням.
- На уровне справа налево каждое значение ставим перед уже записанными, поэтому уровень получается развёрнутым без лишней работы.
- leftToRight меняется после каждого уровня, поэтому направления чередуются, а первый уровень идёт слева направо.
Сложность
Время O(n): каждый узел один раз попадает в очередь и один раз выходит, а addFront на двусторонней очереди — один шаг. Память O(n): в ответе все значения, в очереди не больше двух уровней.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗