Условие задачи

Дано бинарное дерево и требуется обойти его узлы в ширину, т.е. сначала обойти узлы на первом уровне слева направо, затем на втором уровне слева направо и так далее. Необходимо реализовать алгоритм обхода в ширину и вывести значения узлов в порядке обхода.

Примеры

Пример 1

    3
   / \\\\
  9  20
    /  \\\\
   15   7

Вывод: [[3], [9,20], [15,7]]

Пример 2

    1
   / \\\\
  2   3
 /     \\\\
4       5

Вывод: [[1], [2,3], [4,5]]

Решение

1. Начинаем с корня дерева и добавляем его в очередь.
2. Итеративно извлекаем узлы из очереди и добавляем в список узлов на текущем уровне.
3. Если у узла есть левый или правый потомок, добавляем их в очередь.
4. Повторяем шаги 2-3, пока очередь не станет пустой.

Объяснение с примером

Рассмотрим пример дерева:

    3
   / \\\\
  9  20
    /  \\\\
   15   7

1. Начинаем с корня дерева и добавляем его в очередь: [3]
2. Извлекаем узел из очереди и добавляем его в список узлов на текущем уровне: [[3]]
3. Добавляем левого потомка узла 3 (узел 9) в очередь: [9]