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