Проверить полноту двоичного дерева

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

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

Пример:

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

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

Решение. Для решения будем использовать поиск в ширину. Я описал алгоритм поиска в ширину тут: BFS.

Почему поиск в ширину?
Потому что он позволяет обходить граф по слоям. Вначале первую вершину (root), потом всем соседей (в случае с деревом это дети), потом всех соседей соседей (детей всех детей) и т.д. В случае с деревом этот алгоритм будет проходить дерево слой за слоем. И мы можем смотреть на каждый слой, заполнен он или нет так как нам нужно.

Небольшая справка по деревьям.

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

Класс вершины двоичного дерева можно описать на 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

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

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

Само решение на 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;
        }
    }