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