DEV Community

faangmaster
faangmaster

Posted on

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

Ссылка на задачу на 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;
      }
    }
Enter fullscreen mode Exit fullscreen mode

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;
        }
    }
Enter fullscreen mode Exit fullscreen mode

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More