Обход бинарного дерева по слоям/уровням
Published: 2023-11-25 22:12:22


Ссылка на задачу на leetcode: [https://leetcode.com/problems/binary-tree-level-order-traversal/description/](https://leetcode.com/problems/binary-tree-level-order-traversal/description/)

**Условие.** Дано двоичное дерево. Нужно обойти его по слоям/уровням. Каждый уровень обходить слева направо. Результат вернуть в виде списка списков. Каждый вложенный список это элементы одного уровня.

Например:

Для такого дерева

![](https://cdn-images-1.medium.com/max/2000/1*K_QODPM0I1CA8XRxjbB64g.png)

Ответ: [[1], [2, 3], [3, 4, 5], [6]]

**Решение.** Для решения будем использовать поиск в ширину. Я описал алгоритм поиска в ширину тут: [BFS](https://dev.to/faangmaster/poisk-v-shirinu-breadth-first-search-3kaa).

Небольшая справка по деревьям.
>  Граф — это множество вершин и связей между ними.
>  Дерево — это связный граф, не содержащий циклов. Это древовидная структура, в которой есть корень, которой содержит ноль входящих ребер, а остальные вершины имеют ровно одно входящее ребро.
>  Двоичное дерево — дерево, в котором каждая вершина имеет не более двух дочерних вершин.

Класс вершины двоичного дерева можно описать на Java следующим образом:

```java
    class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
    
      public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val= val;
        this.left = left;
        this.right = right;
      }
    }
```

left и right — это левый и правый ребенок вершины. Для простоты, на собеседованиях можно не объявлять поля private и не использовать геттеры для получения доступа к полям. Это позволит обращаться к полям как node.left, node.right.

Вернемся к задаче.

Как я уже сказал, мы будем использовать BFS. **Для случая дерева** его можно упростить. **Нам не нужно использовать visited**. Т.к. мы будем идти от родителей к детям. Вечного цикла у нас не возникнет.

Чтобы понять когда у нас начался и закончился уровень, который мы обходим, нам нужно хранить в очереди номер уровня или элементы каждого уровня складывать в отдельную очередь.

Рассмотрим второй вариант, с отдельной очередью для каждого уровня. Поместим корень дерева в очередь. Создадим еще одну очередь для следующего уровня. Будем итерироваться по первой очереди, пока она не закончится, но помещать детей не в ту же самую очередь, а во вторую. Как только первая очередь закончится — заменим ее второй и повторим весь процесс.

Решение на Java:

```java
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            if (root != null)
                queue.add(root);
            while (!queue.isEmpty()) {
                //Вторая очередь для следующего уровня
                Queue<TreeNode> newQueue = new LinkedList<>();
                //Тут будем хранить элементы одного уровня
                List<Integer> values = new ArrayList<>();
                //Цикл по первой очереди, но детей помещаем во вторую очередь
                while (!queue.isEmpty()) {
                    TreeNode node = queue.poll();
                    values.add(node.val);
                    if (node.left != null)
                        newQueue.add(node.left);
                    if (node.right != null)
                        newQueue.add(node.right);
                }
                result.add(values);
                //Подменяем первую очередь второй
                queue = newQueue;
            }
            return result;
        }
    }
```