Проверить полноту двоичного дерева
Published: 2023-11-25 22:09:11


Ссылка на задачу на leetcode: [https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/](https://leetcode.com/problems/check-completeness-of-a-binary-tree/description/)

**Условие**. Дано двоичное дерево. Нужно проверить его полноту. Полным называется дерево, в котором заполнены все уровни, за исключением быть может только последнего уровня. При этом на последнем уровне все вершины расположены как можно левее.

Пример:

 1. Полное двоичное дерево.

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

2. Неполное двоичное дерево

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

**Решение.** Для решения будем использовать поиск в ширину. Я описал алгоритм поиска в ширину тут: [BFS](https://dev.to/faangmaster/poisk-v-shirinu-breadth-first-search-3kaa).
>  Почему поиск в ширину?
>  Потому что он позволяет обходить граф по слоям. Вначале первую вершину (root), потом всем соседей (в случае с деревом это дети), потом всех соседей соседей (детей всех детей) и т.д. В случае с деревом этот алгоритм будет проходить дерево слой за слоем. И мы можем смотреть на каждый слой, заполнен он или нет так как нам нужно.

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

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

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

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

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

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

Следующий момент. Нам нужно использовать **очередь, в которую можно положить null**, чтобы обнаружить случай отсутствия ребенка. В моем описании BFS я использовать **ArrayDeque** в качестве очереди. Но она **не позволяет добавлять null** в качестве вершины. Поэтому я буду использовать **LinkedList в качестве очереди**. Смотри мою статью про коллекции в Java: [https://telegra.ph/Ierarhiya-kollekcij-v-Java-05-08](https://telegra.ph/Ierarhiya-kollekcij-v-Java-05-08)

И последний момент. Когда будем обходить дерево по слоям, как только мы нашли **отсутствие вершины (null) мы выставим специальный флаг(lastLevel) в true.** **Если при выставленном флаге lastLevel у нас встретилась не null вершина, значит у нас дерево неполное.** Т.е. случай когда был пропуск вершины, а потом снова вершина появилась, как на второй картинке.

**Запомните этот трюк с флагом. Он очень часто используется в алгоритмических задачах. Особенно, если в условии есть что-то типа: “все элементы, кроме одного”, “проверить правильность чего-то, но можно одно исправление” и т.д.**

Само решение на Java:

```java
    class Solution {
        public boolean isCompleteTree(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            boolean lastLevel = false;
            while (!queue.isEmpty()) {
                TreeNode node = queue.poll();
                if (node == null) {
                    lastLevel = true;
                    continue;
                } else if (lastLevel) {
                    return false;
                }
                queue.add(node.left);
                queue.add(node.right);
            }
            return true;
        }
    }
```